Algorithme d'analyse Question
https://stackoverflow.com/questions/1066660
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
NOTE:. Je suis ultra-débutant sur l'analyse de l'algorithme alors ne prenez pas de mes affirmations comme des vérités absolues, tout (ou tout) que je déclare peut-être tort
Salut, je lis sur l'analyse de l'algorithme et « Big-O-notation » et je suis tombé perplexe sur quelque chose.
Supposons que vous êtes invité à imprimer toutes les permutations d'un tableau de caractères, pour [a, b, c] ils seraient ab, ac, ba, bc, ca et cb.
Eh bien une façon de le faire serait (en Java):
for(int i = 0; i < arr.length; i++)
for(int q = 0; q < arr.length; q++)
if(i != q)
System.out.println(arr[i] + " " + arr[q]);
Cet algorithme a une notation de O (n 2 ) si je ne me trompe pas.
Je pensais autre façon de le faire:
for(int i = 0; i < arr.length; i++)
for(int q = i+1; q < arr.length; q++)
{
System.out.println(arr[i] + " " + arr[q]);
System.out.println(arr[q] + " " + arr[i]);
}
Cet algorithme est deux fois plus rapide que l'original , mais à moins que je me trompe, pour le grand-O-notation, il est aussi un O ( 2 )
Est-ce exact? Il est probablement pas si je vais reformuler ma question: Où suis-je mal ??
La solution
Vous avez raison. O notation vous donne une idée de la façon dont les échelles de l'algorithme, pas la vitesse absolue. Si vous ajoutez plus de possibilités, les deux solutions échelle de la même façon, mais on sera toujours deux fois plus vite que l'autre.
O (n) opérations peuvent également être plus lente que O (n ^ 2), pour les opérations suffisamment petite 'n'. Imaginez votre calcul O (n) implique de prendre 5 racines carrées, et votre solution O (n ^ 2) est une seule comparaison. L'opération O (n ^ 2) sera plus rapide pour les petits ensembles de données. Mais lorsque n = 1000, et que vous faites 5000 racines carrées, mais 1000000 comparaisons, puis l'O (n) peut commencer à chercher mieux.
Autres conseils
Je pense que la plupart des gens sont d'accord premier est O (n ^ 2). boucle externe court n fois et exécute n temps de boucle interne chaque exécution de la boucle extérieure. Ainsi, le temps d'exécution est O (n * n), O (n ^ 2).
Le second est O (n ^ 2) parce que les essais n fois de boucle externe. Les boucles internes fonctionne n-1 fois. En moyenne pour cet algorithme, boucle interne court n / 2 fois pour chaque boucle extérieure. de sorte que le temps d'exécution de cet algorithme est O (n * n / 2) => O (1/2 * n ^ 2) => O (n ^ 2).
notation Big-O ne dit rien sur la vitesse de l'algorithme, sauf pour la vitesse, il est par rapport à lui-même lorsque la taille des changements d'entrée.
Un algorithme peut être O (1) encore prendre un million d'années. Un autre algorithme pourrait être O (n ^ 2), mais être plus rapide qu'un algorithme O (n) pour les petites n.
Certaines des réponses à href="https://stackoverflow.com/questions/941283/when-does-big-o-notation-fail"> peut aider à cet aspect de notation grand-O. Les réponses à cette question peuvent également être utiles.
Ignorer le problème d'appeler votre sortie de programme "permutation":
Big-O-notation omet des coefficients constants. Et 2 est un coefficient constant.
Alors, il n'y a rien de mal pour les programmes deux fois plus rapide que l'original d'avoir le même O ()
Vous avez raison. Deux algorithmes sont équivalents en notation Big O si l'un d'eux prend une quantité constante de temps plus ( « A prend 5 minutes de plus que B »), ou un multiple ( « A prend 5 fois plus que B ») ou les deux ( "A prend 2 fois B plus 30 millisecondes ") pour toutes les tailles d'entrée supplémentaires.
Voici un exemple qui utilise un algorithme différent pour faire FONDAMENTALEMENT une sorte semblable de problème. Tout d'abord, la version plus lente, ce qui ressemble beaucoup à votre exemple original:
boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
for (int j = i; j < arr2.length(); j++) {
if (arr1[i] == arr2[j]) {
arraysHaveAMatch = true;
}
}
}
Cela a O (n ^ 2) le comportement, tout comme l'original (il utilise même le même raccourci que vous avez découvert de commencer l'indice j de l'indice i au lieu de 0). Maintenant, voici une approche différente:
boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
if (set.contains(arr2[j])) {
arraysHaveAMatch = true;
}
}
Maintenant, si vous essayez l'exécution de ces, vous constaterez probablement que la première version est plus rapide. Au moins si vous essayez avec des tableaux de longueur 10. Parce que la deuxième version doit faire face à la création de l'objet HashSet et toutes ses structures de données internes, et parce qu'il doit calculer un code de hachage pour tout entier. Cependant, si vous essayez avec des tableaux de longueur 10000000, vous trouverez une autre histoire. La première version doit examiner environ 50.000.000.000.000 paires de nombres (environ (N * N) / 2); la deuxième version doit effectuer des calculs de fonction de hachage sur environ 20.000.000 nombres (environ 2 * N). Dans ce cas, vous voulez certainement la deuxième version !!
L'idée de base derrière les calculs Big O est (1), il est relativement facile de calculer (vous n'avez pas à vous soucier des détails comme la vitesse de votre CPU est ou quel type de cache L2 il a) et (2) qui se soucie des petits problèmes ... ils sont assez vite quand même: ce sont les gros problèmes qui vous tuer! Ce ne sont pas toujours le cas (parfois il ne importe quel genre de cache que vous avez, et parfois il ne importe comment les choses se produisent sur de petits ensembles de données), mais ils sont assez près de vrai assez souvent pour Big O pour être utile.
Vous avez raison sur les deux être grand-O n au carré, et vous avez prouvé en fait que pour être vrai dans votre question quand vous avez dit « Maintenant, cet algorithme est deux fois aussi vite que l'original. " Deux fois plus rapide des moyens multipliés par 1/2 qui est une constante, donc, par définition, ils sont dans le même ensemble grand-O.
Une façon de penser à Big O est d'examiner dans quelle mesure les différents algorithmes réussiraient même dans des circonstances vraiment injustes. Par exemple, si l'on était en cours d'exécution sur un super-ordinateur très puissant et l'autre était en cours d'exécution sur une montre-bracelet. S'il est possible de choisir un N qui est si grand que même si l'algorithme pire est en cours d'exécution sur un super-ordinateur, la montre-bracelet peut encore terminer premier, ils ont des complexités Big O. Si, d'autre part, vous pouvez voir que le supercalculateur sera toujours gagner, quel que soit l'algorithme vous avez choisi ou la taille de votre N était, alors les deux algorithmes doivent, par définition, ont la même complexité.
Dans vos algorithmes, l'algorithme plus rapide est seulement deux fois plus vite que le premier. Cela ne suffit pas d'un avantage pour la montre-bracelet pour battre le super-ordinateur, même si N était très élevé, 1 million, 1trillion, ou même numéro Graham, la montre de poche pourrait jamais battre l'ordinateur super avec cet algorithme. La même chose serait vrai s'ils échangèrent des algorithmes. Par conséquent, les deux algorithmes, par définition de Big O, ont la même complexité.
Supposons que j'avais un algorithme pour faire la même chose en O ( n ) temps. Supposons maintenant que je vous ai donné aussi un tableau de 10000 caractères. Vos algorithmes prendraient n ^ 2 et (1/2) n ^ 2 temps, ce qui est 100.000.000 et 50.000.000. Mon algorithme prendrait 10.000. Il est clair que le facteur de 1/2 ne fait pas une différence, car le mien est beaucoup plus rapide. n ^ 2 terme est dit les termes moins comme n et 1/2, essentiellement les rendant négligeables.
Le grand-oh notation expriment une famille de fonction, donc dire "cette chose est O (n²)" signifie rien
Ce n'est pas pédanterie, elle est la seule, bonne façon de comprendre ces choses.
O (f) = {g | existe x_0 et c tel que, pour tout x> x 0, g (x) <= f (x) * c}
Maintenant, supposons que vous comptez les étapes que votre algorithme, dans le pire des cas , est-ce en terme de la taille de l'entrée: appeler cette fonction f. Si f \ O (n²), alors vous pouvez dire que votre algorithme a un pire cas de O (n²) (mais aussi O (n³) ou O (2 ^ n)). L'insignifiance des constantes suivent de la définition (voir que c?).
La meilleure façon de comprendre la notation Big-O est d'obtenir la compréhension mathématique de l'idée derrière la notation. Cherchez sens lexicographique du mot « Asymptote »
A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.
Ceci définit le temps d'exécution maximale (imaginaire parce que la ligne asymptote rencontre la courbe à l'infini), donc tout ce que vous faites sera en ce moment-là.
Avec cette idée, vous voudrez peut-être savoir, Big-O, O petite et notation oméga.
Gardez toujours à l'esprit, la notation Big O représente le scénario « pire cas ». Dans votre exemple, le premier algorithme a un cas moyen de boucle externe complète * pleine boucle interne, il est donc n ^ 2 bien sûr. Parce que le second a un cas où il est presque pleine boucle extérieure * pleine boucle interne, il doit être rangé dans la même pile de n ^ 2, puisque c'est le pire des cas. De là, il obtient seulement mieux, et votre moyenne par rapport à la première fonction est beaucoup plus faible. Quoiqu'il en soit, en tant que n augmente, votre temps de fonctions croît de façon exponentielle, et qui est tout Big O vous dit vraiment. Les courbes exponentielles peuvent varier considérablement, mais à la fin de la journée, ils sont tous du même type.
