limite supérieure, limite inférieure
Que signifie pour prouver une limite supérieure ou inférieure à un algorithme?
Vous devez vous connecter pour publier un commentaire.
Que signifie pour prouver une limite supérieure ou inférieure à un algorithme?
Vous devez vous connecter pour publier un commentaire.
La preuve d'une limite supérieure signifie que vous avez prouvé que l'algorithme utilise pas plus de une certaine limite sur une ressource.
Prouvant une limite inférieure signifie que vous avez prouvé que l'algorithme utilise pas moins de une certaine limite sur une ressource.
"Ressource" dans ce contexte pourrait être le temps, la mémoire, la bande passante, ou quelque chose d'autre.
Limites supérieures et inférieures ont à faire avec le minimum et le maximum de la "complexité" d'un algorithme (j'utilise ce mot à dessein, car il a un sens très précis dans l'analyse de la complexité).
Prenez, par exemple, notre vieil ami, le tri à bulles. Dans un cas idéal où toutes les données sont déjà triées, le temps est f(n), une fonction dépend de
n, le nombre d'éléments dans la liste. C'est parce que vous n'avez qu'à faire un passage de l'ensemble de données (avec zéro swaps) afin d'assurer votre liste est triée.Particulièrement mal les cas où les données sont triées dans le sens opposé à l'ordre que vous souhaitez, le temps devient f(n2). C'est parce que chaque passage se déplace d'un élément à la bonne position et vous avez besoin
npasse de le faire tous les éléments.Dans ce cas, les limites supérieure et inférieure sont différents, même si le big-O complexité reste la même.
Comme une part, le tri à bulles est décrié (généralement pour de bonnes raisons), mais il peut faire sens dans certaines circonstances. J'ai réellement l'utiliser dans une application où la majeure partie des données sont déjà triées, et seulement un ou deux articles ont tendance à être ajoutées à un moment à la fin de la liste. Pour ajouter un élément, et avec un reverse-directionnelle de tri à bulles, vous pouvez garantir la nouvelle liste sera triée en un seul passage. Qui illustre la limite inférieure du concept.
En fait, vous pourriez faire une optimisation du tri à bulles qui définit la limite inférieure de f(1), simplement en fournissant un supplément de donnée qui indique si la liste est triée. Vous définissez cette après tri et claire lors de l'ajout d'un élément à la fin.
Quelle que soit la limite (supérieure ou inférieure), nous parlons toujours de le pire des cas, l'entrée que nous pouvons envisager. Par exemple, dans le tri, nous supposons que le pire des cas est un non triés liste d'entrée.
Ma compréhension est que problèmes ont une limite inférieure. Par exemple, nous disons que la limite inférieure de la comparaison de tri \Omega(n log n); nous faisons pas d'hypothèses à propos de ce particulier de comparaison de tri algorithme que nous utilisons. Quel que soit l'algorithme de fusion de tri, tri rapide, etc), nous ne pouvons pas faire mieux que cette borne de \Omega(n log n). Les limites inférieures de nous dire, intuitivement, comment dur un particulier problème est.
Lorsque nous parlons d'un spécifique algorithme, alors nous parlons de la limite supérieure. Par exemple, nous disons que la limite supérieure de tri à bulles est O(n^2) et la limite supérieure de la fusion de tri en O(n log n). La limite supérieure, intuitivement, dites-nous comment bon un particulier algorithme est à même de résoudre le problème.