Определение, является ли Алгоритм O (log n)

25

Я обновляю свою теорию CS и хочу знать, как определить сложность алгоритма O (log n). В частности, есть ли простой способ определить это?

Я знаю, что с O (n) у вас обычно один цикл; O (n ^ 2) - двойная петля; O (n ^ 3) - тройной цикл и т. Д. Как насчет O (log n)?

algorithms complexity big-o Atif
источник

2

stackoverflow.com/questions/749819/… или это действительно длинное чтение: stackoverflow.com/questions/487258/…

wkl

Ах, это то место, куда я не смотрел :)

Atif

32

Я знаю, что с O (n) у вас обычно один цикл; O (n ^ 2) - двойная петля; O (n ^ 3) - тройной цикл и т. Д. Как насчет O (log n)?

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

for (i = 0; i < log2(input.count); i++) {
    doSomething(...);
}

Таким образом, любой алгоритм, в котором количество требуемых операций имеет порядок логарифма размера входных данных, равен O (log n). Важный момент, о котором говорит анализ big-O, заключается в том, как изменяется время выполнения алгоритма относительно размера входных данных: если вы удваиваете размер входных данных, выполняет ли алгоритм еще 1 шаг (O (log n)) вдвое больше шагов (O (n)), в четыре раза больше шагов (O (n ^ 2)) и т. д.

Помогает ли из опыта знать, что алгоритмы, которые многократно разделяют свои входные данные, обычно имеют в качестве компонента своей производительности 'log n'? Конечно. Но не ищите разбиение и не делайте поспешных выводов, что производительность алгоритма равна O (log n) - это может быть что-то вроде O (n log n), что совсем другое.

Калеб
источник

3

Обратите внимание, что более разговорный способ сказать «порядка логарифма размера» - это сказать «порядка числа цифр в размере».

@Caleb фактическое основание логарифма неважно при масштабировании разговора.

@ Калеб, говорящий об абсолютах, не имеет смысла с big-O. Формулировка может понравиться вам лучше: когда число цифр удваивается, количество шагов удваивается.

@ ThorbjørnRavnAndersen Да, именно это означает «логарифм размера». Я не уверен, в чем ваша проблема с этой фразой, за исключением того, что вы решили сказать это по-другому. В принципе, я думаю, что мы согласны.

Калеб

25

Идея состоит в том, что алгоритм заключается в O(log n)том, что вместо прокрутки структуры 1 на 1 вы делите структуру пополам снова и снова и выполняете постоянное количество операций для каждого разделения. Алгоритмы поиска, где пространство ответов продолжает разделяться O(log n). Примером этого является бинарный поиск , где вы продолжаете разбивать упорядоченный массив пополам снова и снова, пока не найдете номер.

Примечание: вам не обязательно разбивать пополам.

Кейси Паттон
источник

1

Что если я разделю входные данные на две части, а затем проведу итерацию 2 ^ (n / 2) раза с остатком, прежде чем разделить его снова? (Конечно, я знаю, что тогда, я просто хотел показать пример, где этот упрощенный подход не работает).

Тамас Селей

@afish Это редкость. Это необычайно редко при поиске.

Donal Fellows

1

@DonalFellows Теория алгоритмов не является эмпирической наукой. И вопрос был не в поиске, а в упоминании о log nсрабатывании бинарных поисковых рефлексов у людей.

Тамас Селей

2

Секционирование не делает алгоритм O (log n), оно (обычно) добавляет коэффициент log n к пределу big-O. Рекурсивные сортировки, такие как heapsort и mergesort, являются прекрасными примерами: они разделяют входные данные, но затем они рекурсивно разделяют оба получающихся раздела. Результатом является O (n log n) производительности.

Калеб

@afish: Хороший вопрос. Моя цель с этим ответом - сделать его как можно более простым, учитывая природу вопроса. Я изменил строку «Вы делите структуру пополам ...» на «Вы делите структуру пополам ... и выполняете постоянное количество операций для каждого разделения», чтобы попытаться объяснить эту точку просто.

Кейси Паттон

2

Типичные примеры - это бинарный поиск. Например, алгоритм двоичного поиска обычно O(log n).

Если у вас есть двоичное дерево поиска, поиск, вставка и удаление - все это O(log n)сложно.

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

Крис Харпер
источник

1

Если вы хотите, чтобы это было так просто, как «один цикл -> O (n), двойной цикл -> O (n ^ 2)», то ответ, вероятно, «Tree -> O (log n)». Точнее прохождение дерева от корня до одного (не всех!) Листа или наоборот. Тем не менее, это все упрощения.

scarfridge
источник

Итак, что не так с моим ответом? Я открыт для конструктивной критики.

шарфридж

0

Вы хотите знать, есть ли простой способ определить, является ли алгоритм O (log N).

Хорошо: просто беги и проверяй время. Запустите его для входов 1.000, 10.000, 100.000 и миллиона.

Если вы видите, что время работы составляет 3,4,5,6 секунды (или несколько кратных), вы можете смело сказать, что это O (log N). Если это больше похоже на: 1,10 100,1000 секунд, то это, вероятно, O (N). И если это 3,450,500000 секунд, то это O (N log N).

Питер Б
источник

Каждый должен дать этот ответ по одному и двум голосам по понятным причинам :-)

gnasher729

Определение, является ли Алгоритм O (log n)

Ответы: