Worst Case Laufzeit von Naive-Algorithmus

Question

Ich bin mir nicht sicher, wie die Worst-Case-Laufzeit eines Algorithmus zu berechnen ist. Ich bin mit der asymptotischen Notation vertraut, bin mir aber nicht sicher, wie ich sie verwenden soll. Ein Beispiel zur Erläuterung sein könnte:

d = (X1 - X2)^2 + (Y1 - Y2)^2 
for i=1 to N-1 do: 
    for j=i+1 to n do: 
    t = (Xi - Xj)^2 + (Yi - Yj)^2 
    if (t < d) then d = t 
return d 

Dies hat Eingängen eines Satzes von N Punkten (X1, Y1) .... (XN, YN) mit N> = 2. Die Ausgabe sollte die quadratische Entfernung des nächsten Punktepaars sein. Wie berechne ich die Laufzeit davon?

Answer 1

Der Algorithmus nimmt alle möglichen Paare von den N Eingängen. Es gibt n (n-1)/2 solche Paare, das ist die Anzahl der Male, die der innere Teil der inneren Schleife ausgeführt wird. Unter der Annahme, dass die arithmetischen Operationen zeitlich konstant sind, ist die Zeitkomplexität somit O (n²).

Beachten Sie, dass es in diesem Algorithmus kein unbekannter Faktor ist, der die Zeitkomplexität beeinflusst, so ist dies sowohl die beste & worst case Zeitkomplexität: θ (n²)