Big O pour les boucles while

J'ai eu cette question pour mon affectation, l'autre jour, mais je n'étais toujours pas sûr si je suis à droite.

for(int i =1; i <n; i++)   //n is some size
{             
    for(j=1; j<i; j++)
    {
        int k=1;

        while (k<n)
        {
           k=k+C;   //where C is a constant and >=2
        }
    }
}

Je sais que les boucles for imbriquées est O(n^2), mais je n'étais pas sûr de la boucle while. Je suppose que tout le code sera O(n^3).

Voulez-vous dire i<n et j<n dans le pour-boucles peut-être? Sinon, la fonction est en O(1).
Je suppose que c'était une faute de frappe
S'il vous plaît corriger les fautes d'orthographe dans la question et le format de manière cohérente.
Désolé, le code d'origine était en Pseudo-code, j'ai dû ré-écrire en java.

OriginalL'auteur user977151 | 2011-10-03

big-o

2

La boucle interne est littéralement O(n/C)=O(n), donc, oui, dans l'ensemble c'est O(n^3) (la deuxième boucle a une limite supérieure de O(n))

Merci pour votre réponse:)

OriginalL'auteur Blindy
2
```
    int k=1;

    while (k<n){
       k=k+C                    //where C is a constant and >=2
    }
```
Cela va prendre (n-1)/C étapes: écrire u = (k-1)/C. Ensuite, k = Cu + 1 et la déclaration devient
```
u=0;
while(u < (n-1)/C) {
    u=u+1
}
```
Donc la boucle while est O(n) (depuis C est constant)

EDIT: laissez-moi essayer de l'expliquer dans l'autre sens.

Commencer avec une variable muette u. La boucle
```
u=0;
while(u < MAX) {
    u = u+1
}
```
s'exécute MAX fois.

Quand vous laissez MAX = (n-1) /C, la boucle est
```
u=0;
while(u < (n-1)/C) {
    u=u+1
}
```
Et qui exécute (n-1)/C fois.

Maintenant, la case u < (n-1)/C est équivalent à C*u < n-1 ou C*u + 1 < n, de sorte que la boucle est équivalent à
```
u=0;
while(C*u + 1 < n) {
    u=u+1
}
```
Maintenant, supposons que nous avons réécrit cette boucle en termes d'une variable k = C * u + 1. Ensuite,
```
u=0;
k=1; //C * 0 + 1 = 1
```
La boucle ressemble à
```
while(C*u + 1 < n) {
while(k < n) {
```
et de la condition intérieure est
```
    u=u+1
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C 
```
Mettant tous ensemble:
```
    int k=1;

    while (k<n){
       k=k+C
    }
```
prend (n-1)/C étapes.

Je ne comprends pas pourquoi vous avez "u". Pouvez-vous élaborer davantage sur ce point?
la chose la plus simple est quelque chose qui se passe d'une étape à la fois. J'ai essayé de refaire l'analyse dans le sens inverse

OriginalL'auteur Foo Bah
1

Formellement, vous pouvez procéder en utilisant la méthodologie suivante (Notation Sigma):

Où a symbolise le nombre constant d'opérations à l'intérieur de la boucle de plus bas niveau (a = 1 si vous voulez compter le nombre exact d'itérations).

Triste de la imgur.com est complètement bloqué par mon sociétés proxy 😐
Pouvez-vous interpréter le code LaTeX? Je peux partager le script avec vous.
Ne pouvez pas trouver une citation de SORTE à ce sujet atm. Personnellement, je pense que ce serait cool (et le Latex pourrait même être indexés, dont un pic peut pas), mais je ne sais pas si d'autres l'apprécient parce qu'il peut confondre les lecteurs de votre article, en fonction de comment vous pouvez l'ajouter, donc je vais le regarder à la maison. [ Peut-être que quelqu'un devrait demander de manière à intégrer une sorte de Latex en html convertisseur (stackoverflow.com/questions/116054/...) ]
Pouvez-vous voir ce qui est généré par ce site: http://www.codecogs.com/latex/eqneditor.php?
oui, le site fonctionne pour moi.

OriginalL'auteur Mohamed Ennahdi El Idrissi
0

Bien, vous devez regarder combien de fois la boucle while corps est exécuté pour une valeur donnée de n et C. Par exemple, n est-10 et C est 3. Le corps de s'exécuter 3 fois: k = 1, k = 4, k = 7. Pour n = 100, C = 2, le corps irait à 50 fois: k = 1,3,5,7,9,...,91,93,95,97,99. C'est une question de comptage par C jusqu'à n. Vous devriez être en mesure de calculer le Big-O de la complexité de cet indice.

Je n'aime pas votre comptage approche de l'infini de séquences (c'est ce que asymptotique signifie d'ailleurs)... Un simple "le nombre de boucles croît linéairement avec n à un taux de 1/2" serait plus facile à comprendre et beaucoup plus précis.

OriginalL'auteur Konstantin Tarashchanskiy

Vous devez vous connecter pour publier un commentaire.