Что «лог» представляет в асимптотической записи?

Question

Я понимаю принципы асимптотической нотации и понимаю, что это значит, когда что-то, например, O (1) или O (n ² ). Но что означает O (log n)? или O (n log n) например?

Answer 1

В журнале кратко "логарифм": http://en.wikipedia.org/wiki/Logarithm

Логарифмы, например, говорят нам, сколько цифр необходимо для представления числа, или сколько уровней имеет сбалансированное дерево, когда вы добавляете в него N элементов.

Answer 2

Проверка: en.wikipedia.org/wiki/Big_O_notation

Помните, что log увеличивается медленнее, чем экспоненциальная функция. Итак, если у вас есть алгоритм n ^ 2, а другой, который делает то же самое, имеет логарифмическую функцию, последний будет более эффективен (в общем случае, не всегда!).

Чтобы оценить сложность функции (или алгоритма), вы должны принимать во внимание выполнение в основном во времени и пространстве. Вы можете оценить функцию или алгоритм с другими параметрами, но изначально эти два будут в порядке.

EDIT : http://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation

Также проверьте алгоритмы сортировки . Даст отличное представление о сложности.

Answer 3

log - математическая функция.Это обратное возведение в степень - log (база 2) 2 ^ n есть n.На практике это лучше, чем n ^ c для любого положительного c (включая дробный c, такой как 1/2 (который является квадратным корнем)).Проверьте Википедию для получения дополнительной информации.