Engångsalgoritm

Inom datorer är en enpasssalgoritm eller enpasssalgoritm en strömningsalgoritm som läser dess indata exakt en gång. Det gör det genom att bearbeta objekt i ordning, utan obegränsad buffring ; den läser in ett block i en ingångsbuffert , bearbetar det och flyttar resultatet till en utmatningsbuffert för varje steg i processen. En engångsalgoritm kräver i allmänhet O ( n ) (se 'big O' notation ) tid och mindre än O ( n ) lagring (vanligtvis O (1)), där n är storleken på ingången. Ett exempel på en engångsalgoritm är Sondiks delvis observerbara Markov-beslutsprocessen .

Exempel på problem som kan lösas med engångsalgoritmer

Med vilken lista som helst som indata:

• Räkna antalet element.

Med en lista med siffror:

• Hitta de k största eller minsta elementen, k givet i förväg.
• Hitta summan , medelvärde , varians och standardavvikelse för elementen i listan. Se även Algoritmer för beräkning av varians .

Givet en lista med symboler från ett alfabet av k symboler, given i förväg.

• Räkna antalet gånger varje symbol visas i ingången.
• Hitta de mest eller minst frekventa elementen.
• Sortera listan efter någon ordning på symbolerna (möjligt eftersom antalet symboler är begränsat).
• Hitta det maximala gapet mellan två förekomster av en given symbol.

Exempel på problem som inte kan lösas med engångsalgoritmer

Med vilken lista som helst som indata:

• Hitta det n :te elementet från slutet (eller rapportera att listan har färre än n element).
• Hitta mittelementet i listan. Detta är dock lösbart med två pass: Pass 1 räknar elementen och pass 2 plockar ut den mellersta.

Med en lista med siffror:

• Hitta medianen .
• Hitta lägena (Detta är inte samma sak som att hitta den vanligaste symbolen från ett begränsat alfabet).
• Sortera listan.
• Räkna antalet objekt större än eller mindre än medelvärdet . Detta kan dock göras i konstant minne med två pass: Godkänd 1 hittar medelvärdet och godkänd 2 gör räkningen.

Tvåpassalgoritmerna ovan är fortfarande strömmande algoritmer men inte enpasssalgoritmer.