Алгоритм Скорости Порядка

Question

Иногда меня полностью обманывают, пытаясь оценить скорость алгоритма с помощью нотации O (x), я имею в виду, что могу действительно указать, когда порядок O (n) или O (mxn), но для тех, которые O (LG (N)) или O (C (Power N)) Я думаю, что я что-то там упускаю ... Итак, каковы ваши советы и рекомендации для быстрой оценки с быстрым упущением из алгоритма?

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

• O (n): если есть простой цикл от 1 до n (или несколько из них, но не вложенные.
• O (mxn): вложенный цикл внутри другого, где пределы m и n.

Заранее спасибо.

Answer 1

Вот сообщение в блоге, которое может помочь:

Стоимость разрушения и восстановления воедино

В этом посте объясняется «основная теорема» для работы с ордерами big-O.

Answer 2

Рекурсивные алгоритмы "разделяй и властвуй" часто бывают O (logN). Алгоритм, который проходит по принципу «разделяй и властвуй», будет O (NlogN).

Answer 3

O (lg (n)) : если ваша проблема уменьшается на некоторую пропорцию n (часто n / 2) на каждом шаге вашего алгоритма, и каждый шаг выполняет постоянную работу. Хороший пример - бинарный поиск, поскольку каждый шаг сокращает размер вашей задачи пополам, выполняя постоянный объем работы (вычислите среднюю точку и сделайте одно сравнение).

Обратите внимание, что n находится на top этой пропорции. Это не то же самое, что уменьшение размера вашей проблемы на 1 / n на каждом шаге. :)

Answer 4

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

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

Answer 5

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

• Каждый вложенный цикл от 0 до X добавляет показатель степени к X, поэтому два цикла (один вложенный в другой) дает X ** 2 (квадратичный).
• Если f (X) вызывает f (X-1) с хвостовой рекурсией, то это обычно соответствует итерации, то есть одному внешнему циклу (O (X)).
• Я видел подпрограммы, которые автор задумывал как итеративные, но где есть и итерация от 0..X И хвостовая рекурсия до X-1; это приводит к квадратичному поведению (O (X ** 2))
• Если f (X) вызывает f (X-1) дважды или более, это приводит к экспоненциальному алгоритму, и вы получаете O (2 ** X) из этого.
• Если f (X) вызывает f (X / 2) дважды, это по сложности соответствует одной итерации (это алгоритм «разделяй и властвуй»). (Это приводит к O (X log X) или O (X) в зависимости от деталей, но я понимаю, что в любом случае я думаю об этом как об одной итерации.)
• Если f использует любую упорядоченную структуру данных (упорядоченный набор, кучу приоритетов и т. Д.), Которая была должным образом реализована, и алгоритм добавляет примерно X объектов в структуру данных, операции представляют собой O (log X). Поэтому, если в цикле происходит постоянное число операций структуры данных, скажем, вы получите O (X * log X).
• Если упорядоченная структура данных реализована неправильно, вы можете получить O (X) вместо O (log X) для отдельных операций.

Некоторые особые случаи:

• Алгоритмы, которые увеличивают строки или области памяти путем добавления к ним, во многих языках несут O (X ** 2) накладные расходы, такие как

  for (i = 0; i < X; i++) { s += "foo"; } // quadratic
  

• Этот типичный вложенный цикл также имеет служебные данные X ** 2:

  for (i = 0; i < X; i++) { for (j = 0; j < i; j++) { ... } } // quadratic
  

• Контейнеры C ++ STL, такие как std :: set и std :: map, имеют издержки O (log X) для почти всех операций

• strlen (s) и другие подобные алгоритмы подсчета, когда они возвращают X, имеют O (X) издержки
• memcpy и т. Д. В результате O (X)
• Существуют опасные по сложности операции, такие как стирание элемента путем сравнения на равенство из связанного списка, которые приводят к O (X) или хуже
• При использовании контейнеров на основе шаблонов убедитесь, что операторы сравнения, упорядочения и т. Д. Работают быстро и не имеют скрытых факторов сложности
• Если вы используете подсчет ссылок, удаление ссылки может быть операцией O (X) в худшем случае, если вы отбрасываете последнюю ссылку в связанный список ссылок, длина которого равна X
• Копирование сложных структур данных в объектно-ориентированных языках может привести к странным асимптотическим сложностям, если процедуры копирования объектов нетривиальны и, например, обновить наборы глобальных объектов

Только мои 2 цента! Надеюсь, это поможет!

Answer 6

В статье Википедии в системе обозначений Big O имеется хороший график порядков общих функций .

Answer 7

Если вы ищете быстрый способ для оценки времени выполнения алгоритма, другие ответы хороши. Если вы хотите получить более подробный ответ, я предлагаю вам взглянуть на « Основная теорема ». В немецкой статье есть хороший стол к этому.

Редактировать: Джон Д. Кук сделал хороший обзор основной теоремы, см. Ссылку его ответ.

Answer 8

Я не большой поклонник ответов на свои вопросы, но я нашел это сегодня и напомнил мне этот ТАК вопрос.

http://bigocheatsheet.com/