Algorytm in situ – Wikipedia, wolna encyklopedia

Algorytm in situ (łac. in situ – w miejscu) – algorytm, który do wykonania potrzebuje stałej ilości pamięci komputera, niezależnej od rozmiaru danych wejściowych. Wszelkie potrzebne do otrzymania wyniku obliczenia są wykonywane w pamięci, do której zostały załadowane dane.

Algorytmy tego typu były cenione nie tylko w czasach, kiedy komputery miały mało pamięci operacyjnej, lecz również obecnie, zwłaszcza tam, gdzie przetwarza się duże ilości danych jak np. w obliczeniach numerycznych.

Wiele algorytmów rekurencyjnych, w których liczba wywołań rekurencyjnych jest zależna od danych, nie może działać w miejscu. Wynika to z faktu, że historia wywołań procedur („drzewo rekurencji”) musi być przechowywana na stosie. Przykładem takiego algorytmu jest sortowanie szybkie.

Wyjątkiem są algorytmy, które, mimo że dokonują wielokrotnie wywołań rekurencyjnych, można doprowadzić odpowiednimi przekształceniami matematycznymi do postaci, w której wszystkie takie wywołania są ogonowe. W takiej sytuacji kompilator może być w stanie uniknąć przechowywania na stosie pełnej historii wywołań. Styl programowania, w którym wykorzystuje się często rekurencję ogonową, jest szczególnie przydatny i często używany w programowaniu funkcyjnym.