Мой вопрос возникает из-за сообщения "Plain English Explanation of Big O". Я не знаю точного значения для логарифмической сложности. Я знаю, что могу сделать регрессию между временем и числом операций и вычислить значение квадрата X и определить так сложность. Тем не менее, я хочу знать метод, чтобы быстро определить его на бумаге.Как узнать, когда Big O является логарифмическим?
Как вы определяете логарифмическую сложность? Есть ли хорошие ориентиры?
Не уверен, что это то, что вы имеете в виду, но ... логарифмическая сложность обычно возникает, когда вы работаете с распределенной структурой данных, как сбалансированное двоичное дерево, которое содержит 1 узел в корне, 2 ребенка, 4 внука, 8 правнуков и т. Д. В основном на каждом уровне количество узлов умножается на некоторый коэффициент (2), но все же только один из них участвует в итерации. Или же в качестве другого примера, цикл, в котором индекс удваивается на каждом шаге:
for (int i = 1; i < N; i *= 2) { ... }
вещи, как, которые являются подписи логарифмической сложности.
Master theorem обычно работает.
Немного сложно подумать, но очень хорошо, как только вы овладеете им. – samoz
Нестрогий, но у вас есть алгоритм, который по существу разделяет работу, которую нужно выполнять пополам на каждой итерации, тогда у вас есть логарифмическая сложность. Классический пример - двоичный поиск.
не обязательно. Я понимаю, что вы пытаетесь понять, но только потому, что вы делите работу пополам, это не значит, что вы получаете логарифмическую сложность, вы даже можете иметь экспоненциальное время. Вы должны обратить внимание на то, как рекомбинируются решения и как решаются разделенные проблемы. Существует много случаев, когда доминирует шаг рекомбинации. См. Мастер-теорему или лучше разрешить повторение без теоремы. Есть много сюрпризов под простым повторением. – unj2
@unjaan: Я думаю, вы меня не понимаете. Я не просто сказал, что разделил работу пополам, я сказал: «Работу нужно выполнять пополам на каждой итерации». Я имею в виду, если на каждом шаге половина работы остается по сравнению с предыдущим шагом, тогда у вас есть логарифмическая сложность (для работы, чтения вычислений). –
Если вы просто хотите узнать о логарифмическом Big Oh, будьте в курсе, когда ваши данные разрезаются на половину каждого шага повторения.
Это связано с тем, что если вы обрабатываете данные размером 1/2, размером с шаг перед ним, это бесконечная серия.
Не обязательно 1/2.1/c работает, пока 'c' является постоянным. –
, но 1/2 более «интуитивно понятный» –
Ну, обычно, когда речь идет о Big O, журнал означает базу журнала 2. – samoz
Вот еще один способ сказать это.
Предположим, что ваш алгоритм является линейным в количестве цифр в размере проблемы. Итак, возможно, у вас есть новый алгоритм для большого количества чисел, которые можно показать как линейные по числу цифр. Таким образом, 20-разрядное число занимает в два раза больше, чем 10-разрядное число, используя ваш алгоритм. У этого была бы сложность журнала. (И это было бы полезно для изобретателя.)
Bisection имеет такое же поведение. Требуется примерно 10 шагов деления пополам, чтобы сократить длину интервала в 1024 = 2^10, но только 20 шагов сократят интервал в 2 раза.
Сложность журнала не всегда означает, что алгоритм быстро устраняет все проблемы. Линейный коэффициент перед O (log (n)) может быть большим. Таким образом, ваш алгоритм может быть ужасен по небольшим проблемам, а не становиться полезным до тех пор, пока размер проблемы не будет значительно большим, чтобы другие алгоритмы умирали экспоненциальной (или полиномиальной) смертью.
Хорошо объяснил большой размер проблемы. –
+1 очень интересно. Я ищу что-то вроде ваших примеров больше. Является ли алгоритм логарифмическим как: for (int i = BIG_number; i> N; i * = 1/2) {...} –
1/2 равно нулю в целых делениях, но если вы используете вместо этого «i/= 2» , да. (Если это конкретный алгоритм, о котором вам интересно, возможно, было бы неплохо включить его в ваш вопрос.) –