Was ist die Zeitkomplexität dieses Codes?
-
29-09-2020 - |
Frage
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.
Lösung
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)!) $ .