Algorithme sensible à la sortie - Output-sensitive algorithm

En informatique , un algorithme sensible à la sortie est un algorithme dont le temps d'exécution dépend de la taille de la sortie, au lieu ou en plus de la taille de l'entrée. Pour certains problèmes où la taille de sortie varie considérablement, par exemple de linéaire dans la taille de l'entrée à quadratique dans la taille de l'entrée, les analyses qui prennent explicitement en compte la taille de sortie peuvent produire de meilleures limites d'exécution qui différencient les algorithmes qui auraient autrement complexité asymptotique identique.

Exemples

Division par soustraction

Un exemple simple d'algorithme sensible à la sortie est donné par l' algorithme de division division par soustraction qui calcule le quotient et le reste de la division de deux entiers positifs en utilisant uniquement l'addition, la soustraction et les comparaisons:

def divide(number: int, divisor: int) -> Tuple[int, int]:
    """Division by subtraction."""
    if not divisor:
        raise ZeroDivisionError
    if number < 1 or divisor < 1:
        raise ValueError(
            f"Positive integers only for "
            f"dividend ({number}) and divisor ({divisor})."
        )
    q = 0
    r = number
    while r >= divisor:
        q += 1
        r -= divisor
    return q, r

Exemple de sortie:

>>> divide(10, 2)
(5, 0)
>>> divide(10, 3)
(3, 1)

Cet algorithme prend Θ (Q) temps, et peut donc être rapide dans les scénarios où le quotient Q est connu pour être petit. Cependant, dans les cas où Q est grand, il est surpassé par des algorithmes plus complexes tels que la division longue .

Géométrie de calcul

Les algorithmes de coque convexe pour trouver la coque convexe d'un ensemble fini de points dans le plan nécessitent un temps Ω ( n log n ) pour n points; même des algorithmes relativement simples comme l' analyse de Graham atteignent cette limite inférieure. Si la coque convexe utilise tous les n points, c'est le mieux que nous puissions faire; cependant, pour de nombreux ensembles de points pratiques, et en particulier pour des ensembles de points aléatoires, le nombre de points h dans la coque convexe est typiquement beaucoup plus petit que n . Par conséquent, les algorithmes sensibles à la sortie tels que l' algorithme de coque convexe ultime et l'algorithme de Chan qui ne nécessitent qu'un temps O ( n log h ) sont considérablement plus rapides pour de tels ensembles de points.

Les algorithmes sensibles à la sortie surviennent fréquemment dans les applications de géométrie de calcul et ont été décrits pour des problèmes tels que la suppression de surface cachée et la résolution des conflits de filtre de plage dans les tables de routeur.

Frank Nielsen décrit un paradigme général d'algorithmes sensibles à la sortie connus sous le nom de regroupement et d'interrogation et donne un tel algorithme pour calculer les cellules d'un diagramme de Voronoi . Nielsen divise ces algorithmes en deux étapes: l'estimation de la taille de sortie, puis la construction de structures de données basées sur cette estimation qui sont interrogées pour construire la solution finale.

Généralisations

Un type plus général d'algorithmes sensibles à la sortie sont les algorithmes d'énumération , qui énumèrent l'ensemble des solutions à un problème. Dans ce contexte, les performances des algorithmes sont également mesurées de manière sensible à la sortie, en plus de mesures plus sensibles, par exemple en limitant le délai entre deux solutions successives quelconques.

Voir également

• Évaluation paresseuse

Les références