complexité temps simple O (nlogn)

Question

Je passe en revue une notation Big O pour une interview et je rencontre ce problème.

for i = 1 to n do: 
    j = i 
    while j < n do: 
    j = 2 * j 

simple droite? la boucle externe fournit n étapes. et chacune de ces étapes nous faisons une seule étape O (1) d'affectation j=i puis log (n-j) ou log (n-i) depuis j = i étape pour la boucle while. Je pensais que la complexité temporelle serait O (nlogn) mais la réponse est O (n).

voici la réponse:

La durée est à peu près la somme suivante: Σ 1 + log (n/i) pour i de 1 à n qui est Θ (n).

Maintenant ça fait longtemps que je suis un peu rouillé. d'où vient log(n/i)? Je connais log(n) - log(i) = log(n/i) mais je pensais que nous nous connectons (n-i) pas log (n) - log (i). et comment la complexité temporelle n'est-elle pas O (nlogn)? Je suis sûr qu'il me manque quelque chose de simple mais je regarde ça depuis des heures maintenant et je commence à perdre la tête.

source: ici est la source de ce problème Berkeley CS 170, Fall 2009, HW 1

modifier: après y avoir réfléchi un peu plus il est logique que la complexité temporelle de la boucle interne est log (n/i). Parce que chaque boucle interne s'exécute n-i fois mais je double chaque boucle. si la boucle interne commençait toujours à 0, nous avons log (n) mais prenons en compte le numéro de la boucle sur lequel nous n'avons pas à boucler, log (i). log (n) - log (i) qui est log (n/i).

Answer 1

Je pense que le log (n/i) provient de la boucle intérieure

Remarquez comment j = i

qui signifie que lorsque i = 2 (permet de dire n = 10)

la boucle interne

while j < n do: 
    j = 2 * j 

ne fonctionnera que j=2-10 où j multilplies se par 2 (d'où le journal) & qu dépassements ickly la valeur de n=10

de sorte que la boucle intérieure court log base 2 n/i times

je courais simple i = 10 dans le code & il ressemble à un temps linéaire parce que la plupart du temps la boucle interne exécute une seule fois. Exemple: lorsque la valeur de i devient telle que si vous la multipliez par 2, vous obtenez plus grand que ou égal à n, vous ne lancez pas la boucle interne plus d'une fois.

donc si n = 10 vous obtenez une exécution dans la boucle interne à partir de i=n/2 (if i=10/2=5) puis j commence par j = 5, est dans la boucle se multiplie une fois avec 2 & la condition de boucle interne while j < n do: échoue.

EDIT: il serait O(n.log(n)) si la valeur de j a commencé avec j = 0 à chaque fois & la boucle intérieure a couru de i à n