Fragen zur Analyse von Zeitkomplexität

Question

Hallo, ich habe einige Zweifel über meine Analyse auf der folgenden zwei Codefragment:

1)

for (i = 1; i <= 1.5n; i++) 
     for (j = n; j >= 2; j--) 
      cout << i, j; 

Die äußere Schleife 1,5 n-mal ausgeführt werden, und die innere Schleife wird n-2 mal ausgeführt. Daher ist die Komplexität O (1,5 n * (n-2) O = (n^2)?

2)

j = 1; 
    while (j < n/2) { 
     i = 1; 
     while (i < j) { 
      cout << j << i; 
      i++; 
     } 
     j++; 
    } 

Die äußere Schleife, während n/2-mal ausgeführt wird, und das Die innere while-Schleife wird 1 + 2 + ... + n/2 mal ausgeführt. Daher ist die Komplexität auch O (n^2)?

Ich war nicht so sicher über meine Analyse des zweiten Problems.

Vielen Dank für die Hilfe!

Answer 1

Sie haben Recht. Die richtige Lösung ist zu zählen.

Beachten Sie, dass:

j = 0; 
while (j < n/2) { 
    j++; 
} 

eine O(n) Komplexität hat, während:

j = 1; 
while (j < n) { 
    j *= 2; 
} 

eine O(log n) Komplexität hat.