limite supérieure, limite inférieure

Question

Que signifie prouver une limite supérieure ou une limite inférieure à un algorithme?

Answer 1

Prouver une limite supérieure signifie que vous avez prouvé que l'algorithme utilisera pas plus que certaines limites imposées à une ressource.

Prouver une limite inférieure signifie que vous avez prouvé que l’algorithme utilisera pas moins de certaines limites imposées à une ressource.

" Ressource " dans ce contexte, il peut s'agir de temps, de mémoire, de bande passante ou de quelque chose d'autre.

Answer 2

Les limites supérieure et inférieure concernent les "complexité" minimale et maximale. d’un algorithme (j’utilise ce mot à bon escient car il a une signification très précise dans l’analyse de complexité).

Prenez, par exemple, notre vieil ami, le type à bulle. Dans un cas idéal où toutes les données sont déjà triées, le temps pris est f (n), fonction dépendant de n , le nombre d'éléments de la liste. En effet, il vous suffit de faire un passage du jeu de données (avec zéro échange) pour vous assurer que votre liste est triée.

Dans un cas particulièrement grave où les données sont triées dans l'ordre inverse de celui souhaité, le temps pris devient f (n ² ). En effet, chaque passe déplace un élément à la bonne position et vous avez besoin de n pour faire tous les éléments.

Dans ce cas, les limites supérieure et inférieure sont différentes, même si la complexité de grand-O reste la même.

En passant, le type de bulle est très décrié (généralement pour de bonnes raisons), mais cela peut avoir un sens dans certaines circonstances. En fait, je l'utilise dans une application où la majeure partie des données est déjà triée et que seuls un ou deux éléments ont tendance à être ajoutés à la fois à la fin de la liste. Pour ajouter un élément et avec un tri à bulles dans le sens inverse, vous pouvez être sûr que la nouvelle liste sera triée en un seul passage. Cela illustre le concept de limite inférieure.

En fait, vous pouvez optimiser le tri à bulle en définissant la limite inférieure sur f (1), simplement en fournissant une donnée supplémentaire indiquant si la liste est triée. Vous devez définir cette option après le tri et l’effacer lors de l’ajout d’un élément à la fin.

Answer 3

Quelle que soit la limite (supérieure ou inférieure), nous parlons toujours de l'entrée dans le pire des cas que nous pouvons considérer. Par exemple, dans le tri, nous supposons que le pire des cas est une liste d'entrées non triée.

Je pense que les problèmes ont une limite inférieure. Par exemple, nous disons que la limite inférieure du tri basé sur la comparaison est \ Omega (n log n); nous ne faisons aucune hypothèse sur le algorithme de tri basé sur la comparaison que nous utilisons. Quel que soit l'algorithme (tri par fusion, tri rapide, etc.), nous ne pouvons pas faire mieux que cette borne de \ Omega (n log n). Les limites inférieures nous indiquent intuitivement à quel point un problème particulier est difficile.

Lorsque nous parlons d'un algorithme spécifique , nous parlons de la limite supérieure. Par exemple, nous disons que la limite supérieure du type de bulle est O (n ^ 2) et que la limite supérieure du type de fusion est O (n log n). Intuitivement, les limites supérieures nous indiquent à quel point un algorithme particulier permet de résoudre le problème.