Big-O-Analyse von beliebig verschachtelten Loops?

Question

Sagen, ich habe k für Schleifen in der folgenden Art und Weise verschachtelt:

for a = 1 to n: 
    for b = 1 to n-a: 
     for c = 1 to n-a-b: 
      for d = 1 to n-a-b-c: 
       O(1) 

für jeden beliebigen k, aber alle k diese Schleifen „teilen“ die Grenze von n Iterationen, miteinander, ist die große-O Komplexität immer noch O (n^k)? Oder ist es eine Bestellung darunter?

Edit: What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? fragt tatsächlich etwas ähnliches, aber es wurde nicht gefragt (noch die Antwort-Adresse), wenn zusätzliche Ebenen der Verschachtelung etwas ändern wird.

Dmitrys Antwort erklärt es sehr gut für mich.

Answer 1

OK, lassen Sie uns sie alle zusammenfassen: mit Induktion Sie herausfinden können, dass die Zahlen von Schleifen (für große n > k) sind:

1. n 
    2. n * (n - 1)/2 
    3. n * (n - 1) * (n - 2)/6 
    ... 
    k. n * (n - 1) * ... * (n - k + 1)/k! 
    ... 

Wie Sie die Komplexität sehen O(n**k) wie Sie haben für alle k gezaubert, vorausgesetzt, dass n groß genug ist (n > k).