Разница между O (n) и O (log (n)) - что лучше и что именно O (log (n))?

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

O (log n) лучше.

Ответ 4

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

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

Ответ 5

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

g (x) = O (f (x)) <= > существует x0 и константа C, что для каждого x > x0, | g (x) | <= C | f (x) |.

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

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