Was ist die Zeitkomplexität dieses Codes?

Question

generasacodicetagpre.

Ich versuche, die Zeitkomplexität dieses Codebildes herauszufinden, da ich daran arbeite, Codierungsfragen und deren Zeitkomplexität zu studieren, und ich habe es geschafft, dieses Permutation-Problem mit der Rekursion zu lösen, wie es erforderlich ist, aber ich frage mich, wie ich es binBestimmen Sie genau den Großer $ O $ Zeitkomplexität dafür, da es sich um eine Mischung aus Rekursion handelt, gefolgt von einer iterativen Schleife.Ich würde mich wirklich einiger hilfreicher Beiträge zu schätzen wissen.

Answer 1

Lassen Sie $ F (n) $ die Antwort für eine Eingabe von Größe $ n $ sein. Dann haben wir folgende Gleichung:

$ f (n)= f (n - 1) + (n - 1)!* n= f (n - 1) + n! $

Das liegt daran, dass Sie die Funktion für eine Eingabe von Größe $ n - 1 $ aufrufen, die $ f (n -1) $ , dann Sie über alle Permutationen der Größe $ n - 1 $ , die es $ (n - 1)! $ Solche Permutationen und dann über die Position des neuen Elements, die es $ n $ solche Positionen gibt.Das gibt uns:

$ f (n)= [\ sum_ {i= 1} ^ n i!] <(n + 1)! $

Sie können dies leicht nach Induktion beweisen. So $ f (n)= o ((n + 1)!) $ .