Big oh Analyse

Question

Code 1:

Je mon avis, ce code est O (n^3) puisque la boucle extérieure court n^2 fois et les séries n fois la boucle intérieure. Selon mon prof, ce code n'est pas O (n^3). Quelqu'un pourrait-il expliquer pourquoi? Je suis vraiment confus.

i, j, sum = 1, 1, 0 

while i < n**3: 
    while j < n: 
    sum = sum + i 
    j += 1 
    i = i + n 

Code 2:

Je pense que ce code est O (n). Quelqu'un pourrait-il confirmer?

i, j, sum = 0, 0, 0 

while i ** 2 < n: 
    while j ** 2 < n: 
    sum += i*j 
    j += 2 
    i += 4 

Answer 1

i, j, sum = 1, 1, 0 

while i < n**3: 
    while j < n: 
    sum = sum + i 
    j += 1 
    i = i + n 

On notera que la boucle interne est exécutée uniquement lors de la première passe de la boucle externe, parce que j est pas réinitialisé comme dans la boucle for. Il est assez évident que le temps de fonctionnement de la boucle interne est exactement n. D'autre part, la boucle externe est exécutée n^2 fois. Pourquoi? Regardez comment i changements: d'abord, il est 1, puis n+1, puis 2n+1, ..., et enfin n^2*n+1, alors i obtient incrémenté n^2 fois. Par conséquent, la durée totale est n + n^2, soit O(n^2).

i, j, sum = 0, 0, 0 

while i ** 2 < n: 
    while j ** 2 < n: 
    sum += i*j 
    j += 2 
    i += 4 

Une analyse similaire comme dans le premier cas, la remarque supplémentaire que la condition while i ** 2 < n équivaut à while i < sqrt(n). La boucle interne est exécutée uniquement pendant le premier passage de la boucle externe et son temps d'exécution est sqrt(n)/2 car j est incrémenté de 2 (pas de 1). boucle extérieure court sqrt(n)/4 fois, de sorte que le temps total de la course est sqrt(n)/2 + sqrt(n)/4, qui est O(sqrt(n)).