Quel est le temps de la complexité de la boucle while?

J'essaie de trouver le temps de la complexité des boucles while et je n'ai aucune idée de par où commencer. Je comprends comment trouver la classe de complexité des boucles for, mais quand il s'agit de boucles while, j'ai complètement perdus. Tous les conseils/conseils sur où commencer?

Voici un exemple de problème:

x = 0;
A[n] = some array of length n;
while (x != A[i]) {
   i++;
}

que voulez-vous dire exactement par "ordre de tout-boucles"?
C'est l'équivalent d'une boucle, en boucle la variable d'index i sur le tableau A. Il a O(n). Gardez à l'esprit que le big-O notation désigne le pire moment possible prises par l'algorithme, et si l'élément souhaité est à la fin du tableau, vous permettra d'exécuter la boucle n fois, et la boucle a un coût constant. Par conséquent, vous exécuterez kn opérations, pour une certaine constante k; par conséquent, la boucle est O(n).
Les gars, ce n'est pas une mauvaise question. J'ai vu des étudiants qui sont nouveaux dans cette machinerie face à ce doute beaucoup, et je pense que c'est raisonnable, surtout pour quelqu'un autodidacte.
La question est raisonnable, mais la formulation est mauvaise. Cela peut être difficile lorsque vous n'êtes pas familier avec le jargon, dans ce cas je suppose que la COOP est à la recherche pour obtenir de l'aide sur la façon de déterminer le moment de la complexité d'une boucle while.
oui, quand j'ai dit "l'ordre", je voulais dire le temps de la complexité. En classe, nous avons généralement se référer à tout ce que "l'ordre" alors que c'est juste ce que j'ai utilisé entendre. Mais, comme je l'ai mentionné, je voulais dire pour qu'il soit considéré comme le "temps de la complexité" ou le "Big-Oh" de la alors en boucle. Mes excuses pour le manque de clarté.

OriginalL'auteur | 2015-11-10

algorithm big-o

5

Quand tu dois faire quelque chose n fois, vous devez le faire n fois. Vous pouvez utiliser un for boucle, un while boucle ou tout ce que votre langage de programmation (ou pseudo-code!) offre.
Grossièrement, big O la notation des commentaires sur la quantité de travail que vous avez à faire, et ne se soucie pas comment faire (un peu moins grossièrement, des observations sur la façon dont la quantité de travail qui doit être fait qui grandit avec l'apport croissant).

Continuez à lire pour plus de détails.

Je pense que vous confondez les choses ici.
for et while de la programmation des constructions d'un langage pour exprimer les opérations qui doivent être répétées.

Algorithme d'analyse est agnostique de la langue, de la mise en œuvre, et ne s'inquiètent pas au sujet de la réelle constructions vous utilisez tout en exprimant l'algorithme.

Considérez ce qui suit:
```
1. Input n
2. Do OperationX n times
```
Le Big O la notation des machines vous aide dans ses commentaires sur la complexité de l'opération ci-dessus. Cela permet dans de nombreux cas. Par exemple, il peut vous aider à comparer le temps d'exécution de l'opération ci-dessus avec les éléments suivants:
```
1. Input n
2. Input m
3. Repeat m OperationX n times.
```
Le Big O la notation de vous dire que le premier est en O(n) et le dernier est de O(m * n) (en supposant que OperationX prend un temps constant).

Vous pouvez écrire le code à l'aide de la boucle de construire de votre choix, il n'a pas d'importance.
```
for(int i = 0; i < n; i++) {
    operationX;
}
```
Est la première opération, et
```
i = j = 0;
while(i < n) {
    j = 0;
    while(j < m) {
      operationX;
      j++;
    }
    i++;
}
```
la seconde. Le big O la notation n'a pas vraiment d'importance si le pour et tout a basculé.
```
A[n] = some array of length n;
for(x = 0;x != A[i];i++) {

}
```
Est un for ré-écriture de votre question avec la même complexité (O(n)).

Du sens. Maintenant, dans ce cas précis, est-il correct de dire que la boucle while est de O(n), basé sur ce que @Eric a dit ci-dessus?
Dans le pire des cas, vous pourriez avoir à parcourir l'ensemble de la matrice, et donc la complexité est en effet O(n).
Wow, qui prend tout son sens maintenant. C'est en fait beaucoup plus simple que j'ai d'abord pensé qu'il serait. Merci pour l'aide!
À tout moment. Bonne chance.
Oui, un linéaire de recherche a O(n) complexité, sauf si ces éléments sont connus pour être ordonnées de façon à ce que le moyen position d'arrêt est quelque chose de moins que n/2. par exemple, si vous êtes à la recherche pour les choses qui ont généralement été récemment ajouté à l'arrière de votre tableau (et vous recherchez de l'arrière vers l'avant), la moyenne des temps d'exécution pourrait être O(1), O(log n), O(sqrt n), ou quoi que ce soit d'autre en fonction de ce que vous pouvez prouver sur l'endroit où l'élément cible. Vous pourriez avoir quelque chose à O(n) le pire des cas, mais O(1) moyenne des cas (comme l'ajout d'une table de hachage, où l'ajout de N éléments prend O(N) le temps).

OriginalL'auteur axiom

Vous devez vous connecter pour publier un commentaire.