Время работы алгоритма

Время работы алгоритма (time, T) измеряется в тактах — простейших действиях, а не в секундах. Рядом с ним вторая характеристика — память (memory, M).

Зачем нужно

Пусть алгоритм выполняет $10^9$ тактов. Тогда на трёх компьютерах:

Компьютер	Скорость	Время работы
мой	$10^8$ тактов/с	10 с
бабушкин	$10^7$ тактов/с	100 с
МФТИ	$10^{11}$ тактов/с	0,01 с

Один и тот же алгоритм — от сотых долей секунды до почти двух минут. По секундам сравнивать алгоритмы нельзя: сравнишь компьютеры. Число тактов от компьютера не зависит.

Как работает

RAM-модель и такт

Время считают в RAM-модели. Такт в ней — простейшее действие:

• сравнение;
• присвоение;
• создание переменной.

Время работы — сколько таких действий выполнит алгоритм. Пример подсчёта для цикла — в Циклы.

Не из лекции

RAM — random access machine, «машина с произвольным доступом к памяти». На лекции модель названа, но не расшифрована.

Длина входа

N — длина входа. Алгоритм получает вход, работает на компьютере и выдаёт выход:

N — длина входа   ──вход──▶  [ Алгоритм ]  ──выход──▶
                               компьютер
                           memory: доп. память

Кроме входа и выхода алгоритму может понадобиться дополнительная память. Её оценивают так же, как время.

Зависимость от длины входа

Число тактов растёт с N. По замерам получается ломаная с колебаниями, но интересна тенденция — плавный рост, который эта ломаная повторяет. Тенденцию описывают Асимптотические оценки: $O$, $\Omega$, $\Theta$.

Тонкости

• Для сравнения алгоритмов точное число тактов (например, $3+2N$) не нужно: важен порядок роста, константы отбрасываются — см. Асимптотические оценки.
• В проверке числа на простоту из АиСД L01 оценка записана не через длину входа, а через само число $p$ — там это отмечено отдельно.

Частые ошибки

• Сравнивать алгоритмы по секундам, замеренным на своём компьютере.
• Считать, что быстрый компьютер решает проблему медленного алгоритма: при $N=10^8$ квадратичный алгоритм работает около $10^8$ секунд даже на машине, делающей $10^8$ тактов в секунду.

Углубление — АиСД L03

Дополнительная память $M(N)$ стала одним из трёх свойств, по которым сравнивают сортировки, — рядом с $T(N)$ и устойчивостью. У сортировок выбором, вставками и пузырьком $M(N)=O(1)$: они переставляют элементы внутри самого массива, держа сбоку только счётчики и временную переменную для swap.

Не из лекции: память решета

Решето Эратосфена хранит таблицу на $N+1$ элемент: $M(N)=O(N)$. Здесь память растёт вместе со входом — за скорость платят памятью.

Углубление — АиСД L04

Что считается дополнительной памятью

У функции слияния Merge на лекции записано $M(N)=O(1)$ с пояснением: «A, B, result созданы не нами». Дополнительная память — только то, что алгоритм выделяет сам. Вход и место под ответ, которые передал вызывающий, не считаются. Сортировка слиянием целиком сама выделяет буфер на N элементов, поэтому у неё $M(N)=O(N)$.

Не из лекции: память рекурсии

Рекурсия тоже тратит память, хотя явно её никто не выделяет. Каждый незавершённый вызов лежит на стеке вызовов, поэтому память — это глубина рекурсии. У рекурсивного факториала $M(N)=O(N)$, у сортировки слиянием стек — $O(\log N)$, меньше буфера. Стек в Linux по умолчанию 8 МБ: рекурсия глубиной $10^6$ на C++ падает.