On 2012-11-23, slawek <s...@h...pl> wrote:
> Ok, załóżmy że plik jest 1GB, a RAM mamy 10 razy mniej, czyli 128 MB - i nie
> ma że jakaś wirtualna czy coś. Ewentualnie 100 GB plik i 10 GB RAM.

No i widzisz. Kolejne doprecyzowanie i (dodając informację wcześniejszą)
wiemu już, że dopuszczasz rozwiązania z liniową złożonością obliczeniową
i liniową pamięciową (choć z pewnym maksymalnym współczynnikiem
w okolicy 0.1). To są bardzo istotne informacje.
Z kolei to co napisałeś o gigabajtach istotne nie jest. Ktoś mógłby
spytać "a co gdy plik ma 100TB?". Z 10TB RAMu może być problem.
Asymptotycznie mogłoby się okazać, że potrzebujesz algorytmu
ze stałą pamięcią i to byłby jeszcze większy problem niż z tymi
10TB pamięci :].

> Uwaga: zakładamy że algorytm jest jawnie znany i że dostaniemy możliwie
> "złośliwie skomponowany" plik - czyli najgorszy przypadek (jakkolwiek byłby
> on małoprawdopodobny).

Nie bardzo rozumiem "algorytm jest jawnie znany". Jak ktoś miałby Ci
podać rozwiązanie z niejawnym algorytmem?

Co do reszty (najbardziej skomplikowanych itp), to się nazywa wariantem
pesymistycznym i w algorytmice rozwiązanie jest poprawne wtedy, gdy
działa dla wszystkich dopuszczonych danych wejściowych.

> Ja nie deprecjonuję kartki - tylko deprecjonuję zwykły długopis. Ołówek jest
> lepszy!

Kwestia podejścia. Ja jestem zwolennikiem wariantu
kartka+długopis+śmietnik. Choćby dlatego, że mam pełną historię procesu
rozwiązywania (do debugowania i odzyskiwania). Tylko trzeba mieć dwa
śmietniki, żeby nie mieszać logów ze skórkami z bananów.

pozdrawiam,
PK