Как научиться определять алгоритмическую сложность "на глазок"?

748
2
0
9 мая
23:18
май
2016

Когда речь идёт о более-менее простых алгоритмах, всё и так довольно очевидно - например, какой-то алгоритм вызывается в цикле, число итераций которого не превосходит n, то итоговая асимптотика выйдет O(n*k), где k - время выполнения алгоритма.

Менее тривиальными являются рекурсивные алгоритмы, а также такие, для оценки сложности которых нужен амортизационный анализ. Для рекурсивных алгоритмов есть основная теорема, а также, например, теорема Акра-Баззи, но они не очень интуитивны и не очень часто встречаются на практике. 

Можно их оценивать через дерево рекурсии - создаёте дерево рекурсивных вызовов, в вершинах которого записываете величину, равную числу действий, которые будут сделаны в этом запуске, не включая рекурсивных. Далее нужно просуммировать эту величину по всем вершинам. Часто на одной высоте в вершинах записано одно и то же обозначение, поэтому суммируется на самом деле некий ряд, оценить асимптотику которого уже обычно не так сложно.

Амортизационный анализ нужен в тех случаях, когда алгоритм на любом отдельном шаге может работать долго, но его суммарное время работы гарантированно окажется лучше, чем худшее время работы на одном шаге, умноженное на число шагов. Он часто делается через потенциалы - мы вводим какую-то величину, которая за одно действие не может сильно измениться и на основании её изменения за весь алгоритм, можем сделать вывод о числе действий. 

Например, рассмотрим алгоритм двух указателей - изначально два указателя находятся на первом элементе массива. Далее второй монотонно пробегает все элементы, а первый его догоняет, делая неопределённое число шагов на каждой итерации. Возьмём в качестве потенциала разность между указателями. В начале она равна 0, а в конце не превышает n. При этом на каждом шаге она может либо увеличиться на 1, если первый указатель не сдвинулся с места, либо сократиться на неопределенное число. Но каждому сокращению должно предшествовать увеличение, так как это расстояние - неотрицательная функция. Увеличения может быть не больше n, значит, суммарное число сокращений также не превосходит n и общая асимптотика выйдет O(n).

Это всё совсем базовые приёмы, более глубокое понимание же должно прийти с практикой. Ну и, конечно, стоит просто изучить много алгоритмов, знать и понимать, как доказывается асимптотика для них.

Александр КульковОтвечает на ваши вопросы в своейПрямой линии
16
2
4 августа
14:48

"На глазок" это не всегда возможно сделать. Тем более, что в некоторых случаях важна не только алгоритмическая сложность, но и количество занимаемой памяти, а также сложность в "плохом случае". Тем не менее, есть несколько приемов, но для их применения придется хотя бы поверхностно разобраться в работе алгоритма.

Первое, что нужно понять: из определения О-нотации следует, что O(n/2) или O(5*n)  это то же самое, что O(n), т.е. умножение на ненулевую константу следует убирать из-под О. Отсюда же следует, например, что O(log2(n)) = O(ln(n)).

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

Рассмотрим пару алгоритмов, не использующих вложенность:

- Требуется найти конкретное число в неупорядоченном списке чисел, содержащем это число. Иногда оно будет находиться в самом начале, иногда в конце или в середине. В среднем, это потребует n/2 операций сравнения. Но O(n/2) = O(n) - сложность линейная.

- Добавление элемента в дерево поиска, содержащее n элементов. Дерево поиска имеет корень и две ветки. Корень содержит значение (например, число), левая ветка имеет значение меньше корня, а правая - больше. Дальше каждая ветка может раздваиваться на две ветки, и т.д. Если требуется определить, содержит ли дерево искомое значение, нужно посмотреть его в корне, и если его там нет, сделать выбор - продолжить искать в левой ветке, или в правой. И так далее - это удобно делать с помощью рекурсии. Главное, что здесь нужно понять - все ветки дерева, измеряя от корня, будут иметь примерно одинаковую длину (если не учитывать "плохие случаи"). На первом уровне будет один элемент, на втором два, на третьем 2^3, и т.д. Отсюда можно посчитать, что длина ветки (количество уровней) будет примерно равным log2(n). Значит, двигаясь по дереву от корня, придется произвести log2(n) сравнений - значит, сложность алгоритма O(log2(n)) = O(ln(n)) - логарифмическая.

7
2
Если вы знаете ответ на этот вопрос и можете аргументированно его обосновать, не стесняйтесь высказаться
Ответить самому
Выбрать эксперта