Как узнать, когда Big O является логарифмическим?

Question

Мой вопрос возникает из поста "Простое английское объяснение Big O" . Я не знаю точного значения логарифмической сложности. Я знаю, что могу сделать регрессию между временем и количеством операций и вычислить значение X-квадрата, и определить таким образом сложность. Тем не менее, я хочу знать способ быстрого определения этого на бумаге.

Как вы определяете логарифмическую сложность? Есть ли хорошие тесты?

Answer 1

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

Answer 2

Не уверен, что это именно то, что вы имеете в виду, но ... логарифмическая сложность обычно возникает, когда вы работаете с распределенной структурой данных, такой как сбалансированное двоичное дерево, которое содержит 1 узел в корне, 2 дочерних элемента, 4 внуки, 8 правнуков и т. д. В основном на каждом уровне число узлов умножается на некоторый коэффициент (2), но в итерации участвует только один из них. Или, как другой пример, цикл, в котором индекс удваивается на каждом шаге:

for (int i = 1; i < N; i *= 2) { ... }

Подобные вещи являются сигнатурами логарифмической сложности.

Answer 3

Основная теорема обычно работает.

Answer 4

Вот еще один способ сказать это.

Предположим, ваш алгоритм является линейным по количеству цифр в размере задачи. Итак, возможно, у вас есть новый алгоритм для вычисления большого числа, который вы можете показать линейным по количеству цифр. Таким образом, для 20-значного числа требуется вдвое больше времени, чем для 10-значного числа с использованием вашего алгоритма. Это будет иметь сложность журнала. (И это чего-то стоило бы для изобретателя.)

Бисекция имеет такое же поведение. Для сокращения длины интервала с коэффициентом 1024 = 2 ^ 10 требуется примерно 10 шагов деления пополам, но только 20 шагов сокращают интервал с коэффициентом 2 ^ 20.

Сложность журнала не всегда означает, что алгоритм быстр во всех задачах. Линейный коэффициент перед O (log (n)) может быть большим. Таким образом, ваш алгоритм может быть ужасен для небольших задач и не станет полезным, пока размер задачи не станет заметно большим, если другие алгоритмы умрут экспоненциальной (или полиномиальной) смертью.

Answer 5

Если вы просто хотите узнать о логарифмическом Big Oh, будьте начеку, когда ваши данные будут делиться пополам на каждом шаге повторения.

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