13.02.2012 17:12, Иван Лох пишет:
n^2 это в данном случае бесконечность. Понятно, что надо сохранять вектор отступов блоков на первом проходе..
Тут на интересную задачку можно накопать, если не знать про входные данные более ничего :)
Если хранить вектор отступов, то памяти при работе потребуется M = (N/K)*sizeof(off_t)+K, где N — размер файла, K — размер блока, который мы можем распаковываем единовременно. При этом M может оказаться больше, чем размер доступной памяти.
-- Alexander Galanin