Algorytm in situ

Z Wikipedii

Algorytm in situ (łac. in situ - w miejscu) - jest to 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ę olbrzymie ilości danych jak np. w obliczeniach numerycznych.

[edytuj] Rekurencja

Wiele algorytmów rekurencyjnych, w których ilość 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ć w ogólności 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.