Big O La Notation Des Devoirs--Fragment De Code De L'Algorithme D'Analyse?

Pour les devoirs, j'ai été donné le 8 fragments de code d'analyser et de donner un Grand-Oh notation pour le temps d'exécution. 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 est en 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 ainsi

//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 une fois de plus le n * n est me jetant hors

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

O(N) pour le fragment 8

  • Je suis en désaccord avec la "localisée" commentaire. Le calcul de Grand-Oh est un élément central de l'analyse d'algorithme. Spécifiques des exemples de code avec les estimations de la Grande-Oh peut être extrêmement précieux pour les gens qui essaient de devenir à l'aise dans ce domaine.
InformationsquelleAutor 101010110101 | 2008-10-19
  1. 20

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

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

    *edit: Fragment 7 est O(n^5), pas de O(n^4) comme je l'ai déjà pensé. C'est parce que les deux j et k aller de 1 à n * n. Désolé, je n'ai pas compris cela plus tôt.

    • oh ok, je vois ce que vous dites! Donc, pour 5, le n * n signifie que le corps de l'intérieur de la boucle sera exécutée ordre de N^2 fois et la préparation que de l'ordre de N de la boucle externe, l'ensemble, il sera en O(N^3).
    • même idée pour le fragment 7. L'homme le fragment 8 est allé complètement au dessus de ma tête. Désolé si c'est trop demander, mais je suis juste curieux de savoir quel serait le code pour O(Nlog(N)) regardez comme c'est le cas j'ai jamais l'utiliser?
    • Pour un O(nlog(n)) l'algorithme, imaginer une boucle externe qui compte de 1 à n et une boucle interne qui va de 1 à n en multipliant le comptoir par 2 à chaque fois. Cependant, il est extrêmement rare de trouver de tels algorithmes. Le plus commun O(nlog(n)) les algorithmes sont les QuickSort et de Fusion de Tri.
    • ok, donc en gros si je devais mettre une couche extérieure (1 à n) de la boucle autour de fragment 8, je finirais avec un O(n*log(n)) l'algorithme, car l'extérieur O(n) de la boucle interne et de O(log(n)) serait composé à la forme. Merci à tous pour votre aide!
    • Oui. J'avais le code, mais les commentaires ne s'affichent pas de code bien.
    • Attention! Fragment 7 est O(n^5) non O(n^4) parce que la boucle interne est également délimitée par n^2.
    • Aïe, vous avez raison, Dave. Je vais changer ma réponse.
    • Comme peu d'autres à part que vous le savez sans doute déjà, vpotok, fragment 8 fonctionne sur base du log 2 n fois pour n éléments. Mais là encore, personne ne se soucie vraiment de base, il en, afin que nous venons de dire O(log n).
    • on ne se soucie pas que de base il en est?

    InformationsquelleAutor Kyle Cronin
  2. 7

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

    • Merci pour attraper celui
    • Une chose est sûre. C'est l'avantage d'un site collaboratif.
    InformationsquelleAutor Dave L.
  3. 2

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

    InformationsquelleAutor Rob Walker
  4. 0

    Vous semblent être sur la bonne voie. En ce qui concerne le N*N quel effet pensez-vous que cela aurait? Il est un autre facteur de N de sorte qu'il serait susceptible d'être d'un ordre supérieur.

    Juste un avertissement, j'ai vu un autre post de ce genre et c'était extrêmement bas ont voté. Être prudent. Ici est le post.

    • J'ai effectivement upvoted la question, car il (1) a évidemment fait une tentative sérieuse visant à résoudre les problèmes et (2) a été honnête à ce sujet étant un des devoirs.
    • Oh je suis absolument d'accord, c'est une tentative sérieuse sur le problème et une question valable. Je veux juste avertir en cas d'autres réagissent mal. Mais dans ce cas, il devrait être bon.
    InformationsquelleAutor smaclell
  5. 0

    Vous êtes sur la bonne voie, mais voici une astuce de comment les choses pourraient être plus claire le long du chemin. Supposons que vous avez un peu de code :

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

    Droit, tenir compte du fait que vous disposez d'un code à différents niveaux. Dans cet exemple, vous ne pouvez voir les 3 niveaux de la mesure :

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

    À aucun moment vous ne devez essayer de calculer tout-en-1 go. C'est là que la plupart des débutants, en quelque sorte, de l'erreur de calcul. Calculer individuellement pour chaque niveau, puis de le multiplier tous ensemble.

    Bonne chance!

    InformationsquelleAutor Arnab Datta