Ermitteln Sie die Rechenkomplexität des folgenden Algorithmus

Question

s = 0 
for i = 1 to n3 
for j = 1 to i do 
s = s + 1 

was ist mit computational Komplexität gemeint?

Answer 1

Nehmen wir an, jede Operation in diesem Code dauert konstant _i. Dann kann die Laufzeit durch die Summe c 1 + c 2 * n3 + c ausgedrückt werden * i * n3 + c * i * n3. Wir betrachten konstante Koeffizienten als unbedeutend, da sie unabhängig von der Eingabe nur einen konstanten Wert beisteuern. Dies gibt uns Θ (1) + Θ (n3) + Θ (i * n3 + 1) + Θ (i * n3). In diesem Fall ist also die Zeitkomplexität Θ (n3!), Dh dieser Algorithmus läuft in faktorieller Zeit.

Answer 2

berechnen nur einige Werte (wie oft s = s + 1 für jede Iteration von i ausgeführt wird, und summieren) und sehen, was Sie bekommen:

1 + 2 + 3 + ... + n = n * (n + 1)/2 = n^2/2 + n/2 => Komplexität O (n^2).