Сложность алгоритма(пример -подсчета достаточного количества операций)

Под сложностью алгоритма понимается количество выполняемых им арифметических операций (сложение, вычитание, умножение, деление). Это определение не учитывает величину чисел участвующих в вычислениях. Ясно, что перемножить два 100-значных числа сложнее чем два однозначных, хотя при этом выполняется лишь одна математическая операция.

Поэтому учитывают еще и величину чисел, сводя рассмотрение вопроса к битовым операциям, т.е оценивая количество необходимых операций с 0 и 1 в двоичной записи. Сложность алгоритма представляется функцией от длины входа, т.е от функции количества битов N, требуемых для записи входных данных f(N).

Вычислительная сложность алгоритма определяется двумя параметрами: T - временная сложность, S пространственная (требование к памяти).

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив кару города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти

Величина O - это есть порядок вычислительной сложности, это член разложения функции сложности в ряд быстрее всех растущий с ростом .

Пример:

Алгоритм называется:

Постоянным, если его сложность не зависит от n

Линейным, если его временная сложность O(n)

Полиномиальным, если его временная сложность O(n^m), m=const

Экспоненциальным, если O(t ^{f ( N)}), где t=const> 1, f(n) - полиномиальная функция от n.

сравнений арифметических операций по трудоемкости.

Лемма: Пусть n Î N, m Î R - некоторое кольцо.

Для вычисления степени достаточно не более 2[log₂ n] умножений.

Доказательство: Пусть 2^S£ n< 2^S+1, s=[log₂ n]

Запишем n в двоичной системе счисления:

Теперь вынесем степени 1, m, m², …, . Всего S операций. Затем перемножаем степени , их не более S. В итоге получаем, что для вычисления нужно произвести .