Big O Notation Homework - Analyse des algorithmes de fragment de code? [fermé]

Question

Pour les devoirs, on m'a donné les 8 fragments de code suivants pour analyser et donner une notation Big-Oh pour le temps d'exécution. Est-ce que quelqu'un peut me dire si je suis sur la bonne voie?

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

Je pense que O (N) pour le fragment 1

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

O (N) pour le fragment 2 également

//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 rejette un peu alors 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 également

//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 rejette

//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 n * n problèmes, vous devez exécuter le corps de la boucle n * n fois. Il s’agit donc de O (n ^ 2), puis vous le composez avec l’ordre de l’autre code. Le fragment 8 double en réalité le compteur au lieu de l'incrémenter. Par conséquent, plus le problème est important, moins vous aurez à faire de travail supplémentaire, c'est donc O (log (n)).

* edit: Le fragment 7 est O (n ^ 5), pas O (n ^ 4) comme je le pensais auparavant. En effet, j et k vont de 1 à n * n. Désolé de ne pas l'avoir vu plus tôt.

Answer 2

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

Answer 3

Dans le cas 8, essayez d'écrire le nombre d'itérations pour certaines valeurs de N et voyez à quoi ressemble le motif ... ce n'est pas O (N)

Answer 4

Vous semblez être sur la bonne voie. En ce qui concerne le N * N, quel effet cela aurait-il selon vous? C'est un autre facteur de N, donc ce serait probablement un ordre plus élevé.

Juste un avertissement, j'ai vu un autre billet comme celui-ci et il a été extrêmement voté. Faites attention. Ici , c'est la publication.

Answer 5

Vous êtes sur la bonne voie, mais voici un conseil sur la façon dont les choses pourraient devenir plus claires en cours de route. Supposons que vous ayez du code:

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

Bien, considérez le fait que vous avez du code à différents niveaux. Dans cet exemple, vous ne pouvez voir que 3 niveaux à ce jour:

1. La boucle for externe qui va de 0 à n
2. Une autre boucle for allant de 0 à 100
3. Certains codes à l'intérieur, marqués comme ...

À aucun moment, vous ne devriez essayer de tout calculer en une seule fois. 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!