inkrementierten Schleife wird durch variable, Zeitkomplexität

Question

for (int i = 1; i < a; i++){ 
    for(int j = 1; j < b; j = j + a){ 
     Function() <-- O(1) 
    } 
} 

In diesem Fall wird die äußere Schleife B/A 'mal ‚a'times (O (a)), und die innere Schleife ausgeführt wird' ausgeführt werden (O (b/a)).

Dann ist die gesamte Zeit Komplexität O (a * b/a) = O (b)?

Ich bin nicht diese Interpretation richtig ist oder nicht ..

Answer 1

Nun O(a * b/a) = O(b) offensichtlich richtig ist, weil es die Identität genau dort ist: O(b*a/a) = O(b*1) = O(b).

Es scheint jedoch, dass die Zeit Komplexität ist O(a*b*1) (unter der Annahme, Schleife verursacht keine Overheads in der Zeit). Der Rechenaufwand steigt linear mit jeder einzelnen Schleifengröße. Das ist der Grund für O(a*b).

Answer 2

Armen ist richtig, die Antwort ist O (ab). Wir können die Antwort durch diese Schritte erhalten:

O ((a-1) (b-1) (1))

= O (ab-ab + 1), die -a-b +1 kann ignoriert werden.

= O (ab)

Answer 3

Ich denke, es ist eine gute Frage, meine Gedanken

Die ursprüngliche Komplexität O(a) * O(b/a)

ist sein sollte Aber bevor Sie in Abschluss springen, müssen Sie das beurteilen Fälle:

Wenn b <= a, dann O(b/a) = O(1), so O(a) * O(b/a) = O(a)

Wenn b > a, dann O(b/a) = O(b/a), so O(a) * O(b/a) = O(b)

Also diese Fälle kombiniert, würde ich sagen, es ist O(max(a,b))

Answer 4

O(b) ist falsch, da Sie a mal durch die äußere Schleife passieren daher die Antwort muss mindestens O(a) (und für alle, die Sie wissen, b könnte viel kleiner als a sein). Die Antwort sollte sowohl von a als auch b anstelle von b allein abhängen.

sorgfältig Zählen, fahren Sie durch die innere Schleife ceil((b-1)/a) mal, damit die Komplexität ist

O(a*ceil((b-1)/a)) 

Aber

ceil((b-1)/a) <= (b-1)/a + 1 

So

a*ceil((b-1)/a) <= a*((b-1)/a + 1) = b - 1 + a = a + b - 1 

Die 1 ist asymptotisch vernachlässigbar, Daher ist die Komplexität O(a+b).

Seit O(a+b) = O(max(a,b)) stimmt dies mit der Antwort von @shole überein.