Pourquoi est-bulle de tri en O(n^2)?

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

La boucle interne est une itération: n + (n-1) + (n-2) + (n-3) + ... + 1 fois.

La boucle externe est une itération: n fois.

De sorte que vous obtenez n * (la somme des nombres de 1 à n)

N'est pas n * ( n*(n+1)/2 ) = n * (n^2) + n/2 )

Qui serait (n^3) + (n^2)/2 = O(n^3) ?

Je suis positif, je suis en train de faire ce mal. Pourquoi n'est-ce pas O(n^3)?

Vous comptez l'extérieur n deux fois. Votre intérieur de la boucle elle-même est O(n).
Pas pour pinailler, mais l'algorithme de vous montrer, c'est un tri de la Sélection pas tri à Bulles
La semaine dernière, j'ai écrit l'article sur asymptotique de la complexité et, par hasard, j'utilise de tri à bulles comme un exemple. Donner un coup de feu 🙂 (en.algoritmy.net/article/44682/Asymptotic-complexity). Votre erreur est, comme il a bien été dit par Henk, que la boucle interne est O(n). O(n^2) - la somme de l'arithmétique d'ordre est la complexité de chacune des deux boucles ensemble.
Je suis d'accord, ce n'est pas de tri à bulles

OriginalL'auteur ordinary | 2012-07-13

22

Il est exact que la boucle externe itère n fois l'intérieur de la boucle itère n fois, mais vous double-comptage du travail. Si vous comptez le travail total effectué par résumant le travail effectué dans chaque itération de haut-niveau de la boucle, vous obtenez que la première itération ne n, le deuxième n - 1, le troisième, n - 2, etc., depuis le i-ème itération de haut-niveau de la boucle est la boucle interne de faire n - i travail.

Sinon, vous pouvez compter le travail fait en multipliant la quantité de travail effectué par la boucle interne de fois le nombre total de fois que la boucle s'exécute. La boucle interne ne O(n) travail à chaque itération, et à l'extérieur de la boucle s'exécute en O(n) itérations, de sorte que le travail total est O(n²).

Vous faites une erreur en essayant de combiner ces deux stratégies. Il est vrai que la boucle externe ne n travailler la première fois, alors n - 1, n - 2, etc. Cependant, vous ne multipliez pas ce travail par n pour obtenir le total. Que seraient pris en compte à chaque itération n fois. Au lieu de cela, vous pouvez simplement la somme ensemble.

Espérons que cette aide!

Merci beaucoup. Je vois ce que je faisais de mal maintenant
Pourrait être intéressant d'ajouter que Big O décrit le taux de croissance d'un algorithme proportionnel à la taille des entrées qui n'est pas nécessairement la même chose que le montant exact des itérations pris pour l'algorithme à exécuter.
Serait-il exact de dire que BubbleSort complète (n-1)*(n-1) itérations? donc N^2 itérations. C'est le moment de la complexité. Suis-je en droit de supposer cela?
Bubblesort ne fait pas (n-1)*(n-1), il ne boucle Externe (n-1) : boucle interne [(n-1),(n-2),(n-3),...,(2),(1)] Donc on peut dire que buble sorte d'itérations de boucle intérieure [(n-1),(n-2),(n-3),...,(2),(1)] fois. Qui est n(n-1)/2 fois, ce qui n'est pas N^2 fois, Mais en tant qu'utilisateur "user849425" proposé dans le commentaire ci-Dessus, Big O n'est pas un nombre d'itérations.
Big O notations sont si confus. Boucle intérieure N'est O(n-i) et PAS de O(n)

OriginalL'auteur templatetypedef
6

Votre boucle interne est une itération, AU TOTAL, comme vous l'avez dit n + (n-1) + (n-2) + (n-3) + ... + 1 fois. C'est donc O(n + (n-1) + (n-2) + (n-3) + ... + 1) = O(n(n+1)/2) = O(n^2)

Ah juste eu le moment Aha. ty.
Résoudre (n*(n+1))/2 pour n=5 et 15, et non pas 5^2=25. Pas le même.

OriginalL'auteur GL770
1

L'intérieur de la boucle itère n fois(dans le pire des cas):
```
for(int i = front; i < intArray.length; i++)
```
L'extérieur de la boucle itère n fois:
```
for(int front = 0; front < intArray.length; front++)
```
Donc O(n^2)

OriginalL'auteur NominSim
1

Comment vous calculer N...
- Chaque ligne: +1
- Chaque Tour De Boucle *N
  
  De sorte que vous commencez à ajouter des numéros pour votre première boucle maintenant vous avez N+1, vous continuez et vous arrivez N*N ou N^2 pour le moment plus un certain nombre. Arrachant le nombre car il est généralement négligeable par rapport à N.
Assez bien N est une représentation de tous les éléments dans la boucle un peu comme 1,2,3...N. Ainsi, il est tout représentant un nombre pas combien de fois une boucle, en boucle.

OriginalL'auteur Travis Pessetto

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)

OriginalL'auteur winuxguy

-1

Juste pour le plaisir d'avoir une certaine version de Python de tri à bulles...
```
def bubble_sort(input):
    n = len(input)
    iterations = 0
    for i in xrange(n, 1, -1):
        for j in range(0, i - 1):
            iterations += 1
            if input[j] > input[j+1]:
                input[j],input[j+1] = input[j+1],input[j]

    print iterations
    return input
```
Itérations a été ajouté à l'intérieur de la boucle pour compter le montant total d'itérations. Rien à voir avec le tri à bulles.

Le passage d'un tableau de 5 éléments, les résultats dans 15 itérations pas 25. Aussi lors de la pré-triés aussi 15 itérations. Mais la complexité doit également prendre en compte la comparaison et l'échange.

OriginalL'auteur ruralcoder

Vous devez vous connecter pour publier un commentaire.