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

Ответить
Ответить
Комментировать
0
Подписаться
5
2 ответа
Поделиться

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

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

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

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

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

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

Александр Кульковотвечает на ваши вопросы в своейПрямой линии
16
0

Можете пояснить пример про два указателя? Если оба указателя двигаются в одну сторону, то там не только O(n^2), но и O(n), наверно. А если число шагов второго указателя на каждой итерации неопределённое, то что конкретно под этим имеется в виду?

0
Ответить

Ой, конечно же там O(n). Не знаю, почему я написал квадрат, из предыдущего предложения видно, что время линейно. Исправил.

0
Ответить
Прокомментировать

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

Первое, что нужно понять: из определения О-нотации следует, что 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
0

Поправьте меня, но насколько я помню, алгоритмическая сложность считается как раз для "наихудшего случая".

0
Ответить

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

Например, на случайных данных сложность сортировки массива будет:

  • O(n^2) для пузырьковой сортировки

  • O(n*ln(n)) для сортировки бинарным деревом

Но если массив уже отсортирован, то сложность сортировки будет:

  • O(n) для пузырьковой - пройдет один раз, не сделав перестановок

  • O(n^2) для бинарного дерева - дерево будет состоять из одной ветки длины n, соответственно каждый из n вставляемых элементов потребует от 1 до n сравнений

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

0
Ответить
Прокомментировать
Ответить
Читайте также на Яндекс.Кью
Читайте также на Яндекс.Кью