Вопрос по complexity-theory, algorithm, data-structures, big-o, logarithm – Разница между O (n) и O (log (n)) - что лучше и чем конкретно является O (log (n))?

42

Это мой первый курс по структурам данных и каждой лекции / ТА лекции, о которых мы говоримO(log(n)) , Это, вероятно, глупый вопрос, но я был бы признателен, если бы кто-нибудь смог мне объяснить, что именно это означает!

Возможное повторениеstackoverflow.com/questions/487258/… sank
Вау, 1429 голосов? Я буду доволен половиной этого из-за моей ссылки на Википедию. user1311390

Ваш Ответ

6   ответов
0

Формальное определение:

g (x) = O (f (x)) & lt; = & gt; существует x0 и постоянная C, которая для каждого x & gt; x0, | g (x) | & lt; = C | f (x) |.

Таким образом, если вы найдете алгоритм A для задачи P, то его сложность O (f (n)), Вы можете сказать, что число шагов, которые будет выполнять ваш алгоритм, меньше или равно асимптотически равно f (n), когда n обычно является входным размером. (п может быть что угодно)

Для дальнейшего чтения: http: //en.wikipedia.org/wiki/Big_O_notation.

1

Для краткого ответа O (log n) лучше, чем O (n)

Now what exactly is O( log n) ?

Как правило, при обращении к большой записи O,log n относится к логарифму базы-2, (аналогичноln представляет собой основание е логарифмы). Этот логарифм по основанию 2 является инверсией экспоненциальной функции. Экспоненциальная функцияgrows очень быстро, и мы можем интуитивно сделать вывод, что обратное будет делать прямо противоположное, т.е.grows очень медленно.

Например

х =O(log n)

Мы можем представить как,

п =2x

А также

210 = 1024 & # x2192; lg (1024) = 10

220 = 1,048,576 & # x2192; lg (1048576) = 20

230 = 1,073,741,824 & # x2192; lg (1073741824) = 30

Большие приращения вn привести только к очень небольшому увеличению log (n)

С другой стороны, для сложности O (n) мы получаем линейное соотношение

Фактор журнала2n должно быть взято за коэффициент n в любое время.

Чтобы еще больше закрепить это, я наткнулся на пример вАлгоритмы, разблокированные Томасом Корменом

Рассмотрим 2 компьютера: A и B

На обоих компьютерах есть задача поиска в массиве значения Предположим, что массивы содержат 10 миллионов элементов, которые необходимо найти

Компьютер A - этот компьютер может выполнять 1 миллиард команд в секунду, и ожидается, что он выполнит вышеуказанную задачу, используя алгоритм со сложностью O (n). Мы можем приблизить время, которое занимает этот компьютер для выполнения задачи, как

n / (инструкция p секунда) & # x2192; 107/ 10 ^ 9 = 0,01 секунды

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

log (n) / (инструкция p секунда) & # x2192; войти (107)/107 = 0.000002325349

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

Я думаю, что теперь должно быть очень ясно, почему O (log (n)) намного быстрее, чем O (n)

9

Для ввода размераnалгоритмO(n) будет выполнять шаги, пропорциональныеnв то время как другой алгоритмO(log(n)) будет выполнять шаги примерноlog(n).

очевидноlog(n) меньше чемn следовательно алгоритм сложностиO(log(n)) лучше. Так как это будет намного быстрее.

1

O (logn) означает, что максимальное время работы алгоритма пропорционально логарифму входного размера. O (n) означает, что максимальное врем работы алгоритма пропорционально размеру ввода.

в основном O (что-то) является верхней границей количества команд алгоритма (атомарных). следовательно, O (logn) труднее, чем O (n), а также лучше с точки зрения анализа алгоритмов. Но все алгоритмы, которые являются O (logn), также O (n), но не назад ...

Глупо :) отредактировано
"O (n) является более жестким, чем O (logn), и также лучше с точки зрения анализа алгоритмов" ... ясно, что O (log (n)) лучше, чем O (n). Я думаю, что вы имели в виду другой путь.
1

http://en.wikipedia.org/wiki/Big_oh

O (log n) лучше.

66

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

Биг-О нотация не означаетexact уравнение, а скорееbound, Например, выходные данные следующих функций все O (n):

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

Потому что, когда вы увеличиваете х, все их выходы линейно возрастают, если соотношение между 6: 1f(n) а такжеg(n)также будет примерно 6: 1 соотношение междуf(10*n) а такжеg(10*n) и так далее.


Что касаетсяO(n) или жеO(log n) лучше, учтите: еслиn = 1000, затемlog n = 3 (для log-base-10). Какой алгоритм вы бы предпочли запустить: 1000 секунд или 3 секунды?

+1 - самое ясное объяснение возможно в наименьшем количестве слов. Спасибо.
Красиво объяснил. Кроме того, я хотел бы добавить некоторую информацию о том, что такое логарифм даже для тех, кто не знает. войти в информатику означает, что показатель степени мне нужно было бы поднять число 2, чтобы получить n. Итак, представьте, если n = 16. Наш показатель будет намного меньше, чем фактическое значение n. Было бы 4. Надеюсь, что это имеет смысл. В приведенном выше примере Амбер она приводит аналогичный пример, но возводит 10 в степень 3.
Также стоит отметить, что Big-O обычно относится кany связанный, не обязательно самый жесткий (то есть самый маленький g (x) такой, что f (x) = O (g (x))).f(x), g(x), m(x) также O (n ^ 2). Но в контексте анализа производительности мы хотимtightest ограничить (т.е. наименьшую функцию, которая ограничивает кривую производительности данного алгоритма), чтобы получить «наихудший случай»; Идея работы алгоритма.

Похожие вопросы