Limite supérieure vs limite inférieure pour le cas le pire temps d'exécution d'un algorithme

Pour une fonction f(n), g(n) est un limite supérieure (big O) si, pour "assez grand n", f(n)<=c*g(n), pour une constante c. [g domine f]

g(n) est limite inférieure (gros Omega) si, pour "assez grand n", f(n) >= c*g(n), pour une constante c. [f domine g]

Si g(n) est à la fois la limite supérieure et la limite inférieure de f(n) [avec différents c], nous disons que g(n) est serré lié pour f(n) [Big theta]

Exemple d'utilisation pour la limite supérieure, au lieu de serré: quelques fois c'est dur de trouver serré lié, comme pour le fibonacci algorithme récursif. nous avons donc trouver un moyen facile de limite supérieure de O(2^n), facilement. plus d'infos trouvé de réponses dans ce post.

OriginalL'auteur amit

D'abord, parlons des cas. Un cas de entrée une algorithme est associé avec un instance de problème. Pour le problème de tri (où nous voulons trouver une permutation d'un ensemble dans un ordre précis), je peux regarder une instance comme l'ensemble des nombres {1, 5, 4, 2, 6}. Cette série de chiffres seraient à l'entrée d'un algorithme de tri qui vise à résoudre le problème de tri, comme le Tri de Sélection, ou de l'un des d'autres algorithmes de tri . 

Les mêmes ensembles d'entrées peut être donné à n'importe quel algorithme qui veut résoudre un problème. Il n'importe pas quel algorithme de tri j'utilise, l'ensemble des entrées est toujours la même (parce que, par définition, ils sont de toutes les instances d'un même problème). Cependant, un cas donné peut être le meilleur ou le pire pour un algorithme donné. Certains algorithmes effectuent toujours les mêmes, peu importe ce que les entrées sont, mais certains algorithmes pourrait faire de pire sur certains intrants. Toutefois, cela signifie que chaque algorithme a certains dans le meilleur des cas et le pire des cas; nous avons aussi parfois parler de la moyen (en prenant la moyenne de tous les cas) ou de la attendu cas (lorsque nous avons quelque raison de s'attendre à ce que l'un des cas seront plus fréquents que d'autres).

Algorithme Des Exemples De Cas

Le problème de "trouver le minimum d'une liste non triée" fonctionne toujours de la même pour chaque entrée. N'importe quel algorithme intelligent que vous écrivez, vous devez vérifier chaque élément. Il n'a pas d'importance si vous avez une liste de zéros ou une liste de nombres aléatoires ou une liste dont le premier élément est le minimum, vous ne savez pas jusqu'à ce que vous arrivez à la fin. Chaque cas est le même pour cet algorithme, donc le meilleur des cas est le pire des cas, et aussi le moyen de cas et le cas attendus. Si la liste est triée, on pourrait faire mieux, mais c'est un autre problème.

Le problème de "trouver un élément donné dans une liste" est différent. En supposant que vous avez été à l'aide d'un algorithme qui ne un linéaire de marche à travers la liste, il pourrait s'avérer que l'élément donné a été le premier élément de la liste et vous avez terminé immédiatement. Toutefois, il pourrait aussi être le dernier élément de la liste, dans ce cas, vous avez à marcher le tout avant de le trouver. Alors, vous avez eu le meilleur des cas et le pire des cas.

Algorithmes en fonction de la Taille de l'image

Lorsqu'on veut analyser un algorithme, nous algorists penser à tous les cas de figure, nous pouvons lancer à l'algorithme. Généralement, les deux plus intéressants sont le meilleur des cas et au pire des cas. Si vous pensez que des algorithmes d'exécution en fonction de ses entrées, le meilleur des cas est l'entrée qui minimise la fonction et le pire des cas est l'entrée qui maximise la fonction. Je suis l'aide de la "fonction" dans l'Algèbre de mathématiques de sens ici: une série de x/y de paires (paires d'entrées/sorties, ou dans ce cas, "taille de l'image/nombre d'exécution") dessiner une ligne.

Parce que les algorithmes' exécution est fonction de son entrée, nous avons un autre dans le meilleur des cas (et au pire des cas) pour chaque taille d'entrée. Alors, parfois, nous traitons le meilleur des cas, qu'une seule entrée, mais c'est vraiment un ensemble d'entrées (une pour chaque taille d'entrée). Le meilleur des cas et au pire des cas sont très concrets, notamment en ce qui concerne un algorithme donné.

Limites

Maintenant, quels sont les limites? Les limites sont les fonctions que nous utilisons pour comparer une donnée de l'algorithme de la fonction. Il y a un nombre infini de fonctions limites que nous pourrions envisager. Combien de types possibles de lignes que vous pouvez tirer sur un graphique? C'est le nombre de fonctions limites. La plupart des algorists sont généralement intéressés à quelques fonctions spécifiques: des choses comme la fonction constante, la fonction linéaire, la logarthmic fonction, la fonction exponentielle, etc.

La limite supérieure est une fonction qui est assis sur le dessus d'une autre fonction. Une limite inférieure est une fonction qui se trouve sous l'autre fonction. Lorsque nous parlons de Big O et Gros Omega, nous n'avons pas de soins si les limites sont TOUJOURS au-dessus ou au-dessous de l'autre, juste que, après un certain point, ils le sont toujours (parce que parfois, les algorithmes d'obtenir bizarre pour une petite entrée tailles). 

Il y a un nombre infini de possibles limites supérieures pour une fonction donnée, et un nombre infini de possibles limites inférieures pour une fonction donnée. Mais c'est un de ces bizarres des fois quand nous parlons de différentes tailles, les infinis. Pour être une limite supérieure, la fonction ne doit pas être en dessous de l'autre fonction, donc on règle le nombre infini de fonctions ci-dessous d'autres fonctions (il est donc plus petit que l'ensemble de toutes les fonctions possibles).

Bien sûr, juste parce qu'il y a l'infini les limites supérieures, ne signifie pas qu'ils sont tous utiles. La fonction f(∞) est une borne supérieure pour chaque fonction, mais c'est comme dire "j'ai moins de un nombre infini de dollars" - n'est pas particulièrement utile pour déterminer si je suis sans le sou ou d'un millionnaire. Nous sommes donc intéressés à une limite supérieure qui est "serré" (aussi connu comme un "moindre limite supérieure" ou "supremum"), pour lesquels il n'existe aucune limite supérieure.

Meilleur/Pire Des Cas + Inférieure/Limite Supérieure

Nous avons le meilleur/le pire des cas, qui représentent la partie supérieure et inférieure des fonctions de l'un des algorithmes' exécution de la fonction. Nous avons des limites supérieures et inférieures qui représentent d'autres fonctions qui pourraient être au-dessus ou au-dessous de (respectivement) de toute autre fonction. Ils peuvent être combinés pour définir les principales idées sur les algorithmes.

Pire des Cas, la limite Inférieure: Une fonction qui est une limite au-dessous de la algorithmes' exécution de la fonction, lorsque cet algorithme est donné les entrées de maximiser l'algorithme du moment de l'exécution.

Pire des Cas à la limite Supérieure de: Une fonction qui est une limite au-dessus de la algorithmes' exécution de la fonction, lorsque cet algorithme est donné les entrées de maximiser l'algorithme du moment de l'exécution.

Meilleur des Cas limite Inférieure: Une fonction qui est une limite au-dessous de la algorithmes' exécution de la fonction, lorsque cet algorithme est donné les entrées de minimiser l'algorithme du moment de l'exécution.

Meilleur des Cas à la limite Supérieure de: Une fonction qui est une limite au-dessus de la algorithmes' exécution de la fonction, lorsque cet algorithme est donné les entrées de minimiser l'algorithme du moment de l'exécution.

Exemples de Cas Limites

Nous allons donner des exemples concrets d'lorsque nous avons peut-être à propos de chacun de ces:

Pire des Cas, la limite Inférieure: L'exemple classique est ici de comparaison de tri, qui est connue pour être Ω(n log(n)) dans le pire des cas. N'importe quel algorithme de vous imaginer, je peux choisir un ensemble de pire-cas des entrées lequel est le plus serré de la limite inférieure de la fonction est log-linéaire. Vous ne pouvez pas faire un algorithme qui bat qui en partance pour le pire des cas, et vous ne devriez pas la peine d'essayer. C'est le sous-sol de tri. Bien sûr, il y a beaucoup de limites inférieures pour le pire des cas: constant, linéaire, et sublinéaire sont tous des limites inférieures. Mais ils ne sont pas utiles les plus faibles, car il le log-linéaire de la limite inférieure est le plus serré.

Meilleur des Cas limite Inférieure: Le Tri Par Insertion fonctionne en marche par le biais de la liste, et l'insertion de tout de il vient à travers la bonne place. Si la liste est triée, il aura seulement besoin de marcher à travers la liste une fois sans faire toutes les insertions. Cela signifie que le plus serré de la limite inférieure de la meilleure affaire est Ω(n). Vous ne pouvez pas faire mieux que cela, sans sacrifier l'exactitude, parce que vous avez encore besoin d'être capable de marcher à travers la liste (temps linéaire). Cependant, la limite inférieure pour le meilleur des cas c'est mieux que la limite inférieure pour le pire des cas!

Pire des Cas à la limite Supérieure de: Nous sommes souvent intéressé à trouver un serré limite supérieure sur le pire des cas, parce que nous savons comment mal notre algorithme peut fonctionner dans le pire des temps. Le tri par Insertion dans le pire des cas est une liste qui est complètement hors de vue (c'est à dire complètement inversée à partir de son bon de commande). Chaque fois que nous voyons un nouvel élément, nous devons nous déplacer au début de la liste, en poussant tous les éléments de l'avant (ce qui est un temps linéaire de l'opération, et il fait un linéaire nombre de fois conduit à l'équation de comportement). Toutefois, nous en savons encore que ce comportement d'insertion sera O(n2) dans le pire des cas, agissant comme un serré limite supérieure pour le pire des cas. Ce n'est pas grand, mais c'est mieux que la limite supérieure de, disons, exponentielle ou factorielle! Bien sûr, ceux qui sont valides limites supérieures pour le pire des cas, mais encore une fois ce n'est pas aussi utile que de savoir que l'quadratique est serré à la limite supérieure.

Meilleur des Cas à la limite Supérieure de: Quelle est la pire de notre algorithme peut le faire dans le meilleur des cas? Dans l'exemple avant de trouver un élément dans une liste, où le premier élément est notre élément souhaité, la limite supérieure est O(1). Dans le pire des cas, c'est linéaire, mais dans le meilleur des cas, le pire qui peut arriver c'est que c'est toujours constant. Cette idée n'est généralement pas aussi important que le Pire des Cas à la limite Supérieure, à mon avis, parce que nous sommes généralement plus soucieux de traiter avec le pire des cas, pas le meilleur des cas.

Certains de ces exemples sont en fait des Ө, pas seulement O et Ω. Dans d'autres cas, j'ai pu avoir cueilli à la baisse ou à la limite supérieure de fonctions qui n'étaient pas étanche, mais étaient encore qu'une estimation assez pour être utile (rappelez-vous, si nous ne sommes pas d'être serré, j'ai un infini bien dessiner!). Notez qu'il peut être difficile de trouver des exemples intéressants de différents cas liés à des combinaisons, parce que les combinaisons ont une utilité différente.

Idées fausses et de la Terminologie

Fréquemment, vous verrez les gens avec de fausses idées sur ces définitions. En fait, beaucoup de très bonnes Ordinateur Scientifiques vont utiliser ces termes dans un sens large et de façon interchangeable. Cependant, l'idée de cas et les limites SONT distinctes, et que vous feriez bien de vous assurer de les comprendre. Est-ce à dire que la différence viendra dans votre journée-à-jour? Pas de. Mais lorsque vous devez choisir entre quelques algorithmes différents, vous voulez lire les petits caractères sur les cas et les limites. Quelqu'un qui vous disent que leur algorithme a un Meilleur des Cas à la limite Supérieure de O(1) est probablement en train de tirer la laine sur vos yeux, assurez-vous de demander ce qu'est le Pire des Cas, la limite Supérieure est!

OriginalL'auteur Austin Cory Bart