Utgangssensitiv algoritme - Output-sensitive algorithm

I informatikk er en utgangssensitiv algoritme en algoritme hvis driftstid avhenger av størrelsen på utgangen, i stedet for eller i tillegg til størrelsen på inngangen. For visse problemer der utgangsstørrelsen varierer mye, for eksempel fra lineær i størrelsen på inngangen til kvadratisk i størrelsen på inngangen, kan analyser som tar utgangsstørrelsen eksplisitt i betraktning gi bedre kjøretidsgrenser som skiller algoritmer som ellers ville ha identisk asymptotisk kompleksitet.

Eksempler

Inndeling etter subtraksjon

Et enkelt eksempel på en utgangsfølsomt algoritmen er gitt ved divisjon algoritmen divisjon ved subtraksjon som beregner kvotienten og resten av dele to positive heltall med bare addisjon, subtraksjon, og sammenligninger:

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

Eksempel på utgang:

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

Denne algoritmen tar Θ (Q) tid, og kan derfor være rask i scenarier der kvotienten Q er kjent for å være liten. I tilfeller der Q er stor, overgår den imidlertid mer komplekse algoritmer som lang divisjon .

Beregningsgeometri

Konvekse skrogalgoritmer for å finne det konvekse skroget til et endelig sett med punkter i planet krever Ω ( n log n ) tid for n punkter; selv relativt enkle algoritmer som Graham-skanningen oppnår denne nedre grensen. Hvis det konvekse skroget bruker alle n poeng, er dette det beste vi kan gjøre; for mange praktiske sett med punkter, og spesielt for tilfeldige sett med punkter, er imidlertid antall punkter h i det konvekse skroget vanligvis mye mindre enn n . Følgelig er utgangssensitive algoritmer som den ultimate konvekse skrogalgoritmen og Chans algoritme som bare krever O ( n log h ) tid betydelig raskere for slike punktsett.

Utgang følsomme algoritmer oppstår ofte i beregningsorientert geometri programmer og har blitt beskrevet for problemer som skjulte overflaten fjerning og løse utvalg filter konflikter i ruter tabeller.

Frank Nielsen beskriver et generelt paradigme for utgangssensitive algoritmer kjent som gruppering og spørring og gir en slik algoritme for beregning av celler i et Voronoi-diagram . Nielsen deler disse algoritmene i to trinn: estimering av utgangsstørrelsen, og deretter bygges datastrukturer basert på det estimatet som blir spurt om å konstruere den endelige løsningen.

Generaliseringer

En mer generell type utgangssensitive algoritmer er tellingsalgoritmer , som teller settet med løsninger på et problem. I denne sammenheng måles også ytelsen til algoritmer på en utgangssensitiv måte, i tillegg til mer følsomme tiltak, for eksempel begrenset forsinkelsen mellom to påfølgende løsninger.

Se også

• Lat evaluering

Referanser