Computing Worst-Case-Zeit Komplexität mit Algorithmen

Question

Dies ist eine Frage auf meiner Studienführer, aber ich bin mir nicht sicher, wie das Problem zu beginnen, oder sogar was der Code "zu n tun" bedeutet. Ich habe einige andere Fragen beantwortet, die auch auf die Worst-Case-Zeit-Komplexität, aber nichts mit Code ähnlich zu diesem Problem suchen. Ich suche nur nach einem allgemeinen Weg, um diese Probleme zu lösen, also, wenn es eine Methode gibt, würde ich wirklich etwas Hilfe mögen. Die Frage ist unten.

Compute the worst case time complexity of the following algorithm. 

for i = 1 to n do 
    for j = 1 to i do 
     for k = 1 to j do 
      print(i,j,k). 

Answer 1

Es scheint mir, dass es die Komplexität in diesem Fall keine beste oder schlimmste Falles Zeit ist, nur die Zeitkomplexität. Wie in dem Wikipedia-Artikel this erwähnt, sind die besten und schlimmsten Fälle allgemein auf Funktionen wie Sortierfunktionen anwendbar, bei denen die durch den Algorithmus benötigte Zeit davon abhängt, wie die Eingabe anfänglich sortiert wurde. So in Ihrem Fall, nach den Ergebnissen des MATLAB-Code unten, würde ich sagen, dass die Zeit Komplexität ist

1/6*n*(n+1)*(n+2) 

Dies wurde erreicht, indem Sie den Code für verschiedene Werte von n ausgeführt wird, und stellte fest, dass jedes Inkrement n fügt das Dreieck Anzahl von Druckanweisungen, dh

sum_{i = 1}^{n} 1/2*i*(i+1) = 1/6*n*(n+1)*(n+2) 

Code Matlab entsprechen:

n = 5; 

count = 0; 
for i = 1:n 
    for j = 1:i 
     for k = 1:j 
      count = count + 1; 
     end 
    end 
end 

1/6*n*(n+1)*(n+2) 
count 

Answer 2

Diese Frage einige Male bereits beantwortet wurde, können Sie Überprüfen Sie sie here und here für die mathematische Erklärung.

Grundsätzlich, da es sich um eine dreifach verschachtelte Schleife ist, wäre die schlimmste Zeit 0 (n³) sein