Основы анализа алгоритмов

Время выполнения большинства алгоритмов напрямую зависит от размера вводимых данных (т.е. чем больше размер, тем дольше работает алгоритм).

Поэтому вполне логично описать эффективность алгоритма в виде функции от некоторого параметра `n`, связанного с размером входных данных. В большинстве случаев выбрать такой параметр не представляет большого труда.

Например, для задач, связанных с сортировкой и поиском, таким параметром будет размер списка. Но для перемножения матриц существует две подходящих единицы – порядок матрицы `n` и количество перемножаемых элементов в матрицах `K`. Поскольку существует простая формула, связывающая эти две единицы измерения, мы легко можем перейти от одной единицы к другой, однако формула для эффективности алгоритма будет зависеть от того, какая из двух единиц измерения была использована при анализе.

На выбор подходящей системы измерений размера задачи могут повлиять выполняемые рассматриваемым алгоритмом действия. Например, как оценить размер входных данных для алгоритма, выполняющего проверку орфографии? Если в алгоритме проверяется каждый вводимый символ, то оценить размер входных данных мы можем, подсчитав количество символов во входном потоке. Если же в алгоритме происходит обработка текста по словам, то нужно подсчитать количество слов во входном потоке.