Big O Notation Devoirs - Analyse des algorithmes de fragment de code?

Question

Pour les devoirs, on m'a donné les 8 fragments de code suivants pour analyser et donner une notation Big-Oh pour la durée de fonctionnement. Quelqu'un peut-il me dire si je suis sur la bonne voie?

//Fragment 1 
for(int i = 0; i < n; i++) 
    sum++; 

Je pense O (N) pour le fragment 1

//Fragment 2 
for(int i = 0; i < n; i+=2) 
    sum++; 

O (N) pour le fragment 2 ainsi

//Fragment 3 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) 
     sum++; 

O (N^2) pour le fragment 3

//Fragment 4 
for(int i = 0; i < n; i+=2) 
    sum++; 
for(int j = 0; j < n; j++) 
    sum++; 

O (N) pour le fragment 4

//Fragment 5 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < n * n; j++) 
     sum++; 

O (N^2) pour le fragment 5 mais le n * n me jetant un peu, donc je ne suis pas tout à fait sûr

//Fragment 6 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < i; j++) 
     sum++; 

O (N^2) pour le fragment 6 comme bien

//Fragment 7 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < n * n; j++) 
     for(int k = 0; k < j; k++) 
      sum++; 

O (N^3) pour le fragment 7 mais encore une fois le n * n me secouer

//Fragment 8 
for(int i = 1; i < n; i = i * 2) 
    sum++; 

O (N) pour le fragment 8

Answer 1

Je pense que le fragment 5 est O (n^3), et de même le fragment 7 est O (n^5) *. Il ressemble également à O (log (n)) pour le fragment 8.

Pour les problèmes n * n, vous devez exécuter le corps de la boucle n * n fois, donc ce serait O (n^2) , alors vous composez cela avec l'ordre de l'autre code. Fragment 8 double en fait le compteur au lieu de incrémenter, de sorte que le plus grand problème, le travail moins supplémentaire que vous avez à faire, il est donc O (log (n))

* edit: Fragment 7 est O (n^5), pas O (n^4) comme je le pensais précédemment. C'est parce que j et k vont de 1 à n * n. Désolé je n'ai pas attrapé ça plus tôt.

Answer 2

Vous semblez être sur la bonne voie. En ce qui concerne le N * N, quel effet pensez-vous qu'il aurait? C'est un autre facteur de N donc ce serait probablement un ordre supérieur. Juste un avertissement, j'ai vu un autre message comme celui-ci et il a été voté extrêmement bas. Faites attention. Here est la publication.

Answer 3

Pour 8 cas essayer d'écrire le nombre d'itérations pour certaines valeurs de N et de voir ce que le modèle ressemble ... il n'est pas O (N)

Answer 4

Fragment 7 est O (n^5) , pas O (n^4) comme le prétend le commentaire actuellement accepté. Sinon, c'est correct.

Answer 5

Vous êtes sur la bonne voie, mais voici une astuce sur la façon dont les choses pourraient se clarifier en cours de route. Supposons que vous ayez du code:

for(i = 0; i < n; i++) { 
    for(j = 0; j < 100; j++){....} 
} 

À droite, tenez compte du fait que vous avez du code à différents niveaux.Dans cet exemple, vous ne pouvez voir 3 niveaux jusqu'à présent:

1. L'extérieur de la boucle qui va de 0-n
2. Une autre boucle pour qui 0-100
3. Certains code à l'intérieur, cela est marqué comme ...

À aucun moment si vous essayez de calculer tout en 1 go. C'est là que la plupart des débutants font une sorte d'erreur arithmétique. Calculez-le individuellement pour chaque niveau, puis multipliez-le tous ensemble.

Bonne chance!