Outputfølsom algoritme - Output-sensitive algorithm

I datalogi er en outputfølsom algoritme en algoritme, hvis driftstid afhænger af outputstørrelsen i stedet for eller ud over inputstørrelsen. For visse problemer, hvor outputstørrelsen varierer meget, for eksempel fra lineær i størrelsen på input til kvadratisk i størrelsen på input, kan analyser, der tager outputstørrelsen eksplicit i betragtning, producere bedre runtime-grænser, der differentierer algoritmer, der ellers ville have identisk asymptotisk kompleksitet.

Eksempler

Opdeling ved subtraktion

Et simpelt eksempel på et output-følsom algoritme er givet ved division algoritme division med subtraktion som beregner kvotienten og resten af dividere to positive heltal kun bruger addition, subtraktion 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å output:

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

Denne algoritme tager Θ (Q) tid og kan derfor være hurtig i scenarier, hvor kvotienten Q vides at være lille. I tilfælde, hvor Q er stor, overgår den imidlertid mere komplekse algoritmer såsom lang division .

Beregningsgeometri

Konvekse skrogalgoritmer til at finde det konvekse skrog af et endeligt sæt punkter i planet kræver Ω ( n log n ) tid for n point; selv relativt enkle algoritmer som Graham-scan opnår denne nedre grænse. Hvis det konvekse skrog bruger alle n- punkter, er dette det bedste, vi kan gøre; for mange praktiske sæt af punkter og især for tilfældige sæt af punkter er antallet af punkter h i det konvekse skrog imidlertid typisk meget mindre end n . Derfor er outputfølsomme algoritmer, såsom den ultimative konvekse skrogalgoritme og Chan's algoritme, der kun kræver O ( n log h ) tid, betydeligt hurtigere for sådanne punktsæt.

Output-sensitive algoritmer opstår hyppigt i beregningsmæssige geometri applikationer og er blevet beskrevet til problemer såsom skjulte overflade fjernelse og løsning range filter konflikter i router tabeller.

Frank Nielsen beskriver et generelt paradigme for outputfølsomme algoritmer kendt som gruppering og forespørgsel og giver en sådan algoritme til beregning af celler i et Voronoi-diagram . Nielsen opdeler disse algoritmer i to faser: estimering af outputstørrelse og derefter opbygning af datastrukturer baseret på det skøn, der spørges om at konstruere den endelige løsning.

Generaliseringer

En mere generel type outputfølsomme algoritmer er optællingsalgoritmer , der tæller sæt af løsninger på et problem. I denne sammenhæng måles algoritmernes ydeevne også på en outputfølsom måde ud over mere følsomme målinger, f.eks. Begrænset forsinkelsen mellem to på hinanden følgende løsninger.

Se også

• Lazy evaluering

Referencer