Алгоритм линейный по скорости и константный по памяти

[Petrum]

Не могли бы вы пояснить что это именно такое?

[Abstraction]

Пусть у нас есть задача, входные данные для которой могут иметь различный объём - один символ, десять, миллион, миллиард. Обозначим число входных символов как n.
Как правило, время выполнения алгоритма и требуемая в процессе память зависят от n: фотографию 640х480 Windows открывает меньше секунды, а вот 12000х10000 может заставить задуматься. Обозначим зависимость времени от n как T(n), зависимость максимальной требующейся в процессе выполнения памяти от n как M(n).
Под F(n)=O(g(n)) обычно понимают, что существует некоторые фиксированные, не зависящие от n числа A и B, оба строго больше нуля, такие, что при всех n (как вариант, при всех n больше некоторого m) A<F(n)/g(n)<B. Так, например, n^2+3n+15=O(n^2); 1+n/1000000=O(n).
Линейным по скорости называется алгоритм, для которого T(n)=O(n). Константным по памяти - такой, для которого M(n)=O(1).

[Petrum]

Спасибо =)