Как узнать, что большое О является логарифмическим?

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

Bisection имеет такое же поведение.Чтобы сократить длину интервала в 1024 = 2^10, потребуется примерно 10 шагов пополам, но только 20 шагов сократят интервал в 2^20.

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