Подразделы

Другие разделы

Дата и время

18/06/2026 04:40:09

Авторизация

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

Эффективность алгоритмов Оценка размера входных данных Единицы измерения времени выполнения алгоритма Порядок роста Эффективность алгоритма в разных случаях

Оценка размера входных данных

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

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

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

--

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

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

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

Оценка размера входных данных