Форум на Исходниках.RU

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

FasterHarder — Thu, 28 Jul 2011 15:14:44 +0000

FasterHarder: всем пасибо за участие, многое стал понимать лучше... ;)

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

amk — Thu, 28 Jul 2011 11:49:41 +0000

amk: FasterHarder

f(x) = O(g(x)) означает, что при увеличении x отношение f(x)/g(x) остается ограниченным по величине.

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

O(1) - затраты времени не зависят от размера задачи
O(log(n)) - при увеличении размера задачи вдвое, затраты времени меняются на постоянную величину
O(n) - при увеличении размера задачи в 2 раза, затраты времени возрастут тоже в два раза
O(n^2) - при увеличении размера задачи в 2 раза, затраты времени возрастут примерно в четыре раза
O(n*log(n)) - при увеличении задачи в два раза, затраты времени возрастут в два раза, плюс некоторая прибавка, относительный вклад которой уменьшается с ростом n. При малых n может вносить очень большой вклад. O(n*log(n)) начинает расти как квадрат при малых n, но потом рост замедляется почти до линейного
O(n^p) - полиномиальный алгоритмы, остающиеся мечтой для некоторых задач.
O(a^n), O(n!), O(n^n) - неполиномиальные алгоритмы, в порядке ускорения увеличения затрат времени

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

Pacific — Thu, 28 Jul 2011 09:48:32 +0000

Pacific: FasterHarder
В записи O(...) константы перед выражением и величина основания логарифма не имеют значения. Посмотри в википедии определение того, что такое O(f(x)). То есть, коротко говоря, O(3*n) и O(100*n) - одно и то же множество функций. Так же как и O(n*log2(n)) и O(n*log3(n)) - одно и то же множество функций.

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

MBo — Thu, 28 Jul 2011 08:34:07 +0000

MBo: Вся концепция O(f(x)) (а также theta и т.д.) обозначений строится на том, что оценивается максимальная степень аргумента подскобочного выражения без учета констант.
Т.е. выражения x^2, 0.01*x^2 - 500*x, и 10000 * x^2 - 1 имеют общий порядок O(x^2), квадратичный, и выражается это в том, что при больших x увеличение аргумента x в 2 раза даст увеличение значения выражения примерно в 4 раза для любого из выражений данного порядка (одинаковое асимптотическое поведение)

Если в выражение для сложности входит логарифм, то изменение его основания внесет лишь константный множитель, не изменяя асимптотического поведения алгоритма.
пример: n = 10, 100, 1000, 10000
n*log10(n) = 10, 200, 3000, 40000
n*ln(n) = 23, 460, 6900, 92000

Видим, что в обоих случаях переход от n = 10 к 100 вызывает изменение функции (увеличивает время работы алгоритма) в 20 раз, от 1000 к 10000 - в 13.3 раза

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

FasterHarder — Thu, 28 Jul 2011 07:57:12 +0000

FasterHarder: нет, ну понятно, что есть сравнения, перемещения, выделяемая память и все считаться должно в комплексе...

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

Машина — Thu, 28 Jul 2011 07:52:53 +0000

Машина: ОК, имеется в виду, что n*log(n) - примерное кол-во замен в массиве, отсюда вопрос, почему считаем именно их :rolleyes:

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

FasterHarder — Thu, 28 Jul 2011 07:50:02 +0000

FasterHarder:

Цитата Машина @ 28.07.11, 07:48

Ибо что это - кол-во замен в массиве?

хм..я думал, это количество элементов массива, вполне реальная величина...

Добавлено 28.07.11, 07:52

Цитата Машина @ 28.07.11, 07:48

Короче, сложность дает понятие о масштабе сложности, а не о точном его значении.

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

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

Машина — Thu, 28 Jul 2011 07:48:24 +0000

Машина: Заметь, что n - тоже условная хрень. Ибо что это - кол-во замен в массиве? А почему другие операции не считаем?
Короче, сложность дает понятие о масштабе сложности, а не о точном его значении. Это поможет оценить, загнется ли твой алгоритм при растущем n, и как быстро.

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

FasterHarder — Thu, 28 Jul 2011 07:42:52 +0000

FasterHarder: вообще, можно в данном контексте говорить о затраченном времени в секундах (единицах времени), хотя бы условно, на какой либо алгоритм? если да, то пусть при n = 100 и использовании quick sort получим: О(n * log(n))...
и опять таки:
если основание 10, то 100 * log10(100) = 100 * 2 = 200 условных секунд
если основание 2, то 100 * log2(100) = 100 * 6.78 = 678 условных секунд
очевидно, что 200 <> 678!!....

причем здесь n = 1000 / 10000?....

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

Машина — Thu, 28 Jul 2011 07:34:22 +0000

Машина: Ну и? Посчитай теперь для n=1000, n=10000, посмотри, в чем разница.

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

FasterHarder — Thu, 28 Jul 2011 07:31:13 +0000

FasterHarder: не понял!...
допустим, n = 100, пусть применяется быстрая сортировка О (n * log(n)) = O (100 * log100), если основание будет 10, то ответ будет 100 * 2 = 200, если основание будет 3, то примерно (3^4 = 81, пусть будет 100) будет 100 * 4 = 400

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

Машина — Thu, 28 Jul 2011 07:25:29 +0000

Машина: Не имеет значения, т.к. логарифмы с разным основанием отличаются "всего лишь" кратностью на константу.

Не понимаю, что означает O(log (n)) в алгоритмах сортировки

FasterHarder — Thu, 28 Jul 2011 07:21:51 +0000

FasterHarder: Всем привет! Respect!
Вопрос по сортировкам: одним из самых важных факторов оценивания алгоритма является "время" или "вычислительная сложность"...вики пишет, что для типичного способа сортировки хорошим показателем времени является О(n * log(n))...
вопрос: что означает "log" в данном контексте??
логарифм имеет основание и под логарифмическое выражение log_ab, и могут быть сокращения для десятичного логарифма (lg(b)), для натурального (ln(b)), но что такое ПРОСТО log в данном контексте???