Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.128.171.246] |
|
Сообщ.
#1
,
|
|
|
Всем привет! Respect!
Вопрос по сортировкам: одним из самых важных факторов оценивания алгоритма является "время" или "вычислительная сложность"...вики пишет, что для типичного способа сортировки хорошим показателем времени является О(n * log(n))... вопрос: что означает "log" в данном контексте?? логарифм имеет основание и под логарифмическое выражение logab, и могут быть сокращения для десятичного логарифма (lg(b)), для натурального (ln(b)), но что такое ПРОСТО log в данном контексте??? |
Сообщ.
#2
,
|
|
|
Не имеет значения, т.к. логарифмы с разным основанием отличаются "всего лишь" кратностью на константу.
|
Сообщ.
#3
,
|
|
|
не понял!...
допустим, n = 100, пусть применяется быстрая сортировка О (n * log(n)) = O (100 * log100), если основание будет 10, то ответ будет 100 * 2 = 200, если основание будет 3, то примерно (3^4 = 81, пусть будет 100) будет 100 * 4 = 400 |
Сообщ.
#4
,
|
|
|
Ну и? Посчитай теперь для n=1000, n=10000, посмотри, в чем разница.
|
Сообщ.
#5
,
|
|
|
вообще, можно в данном контексте говорить о затраченном времени в секундах (единицах времени), хотя бы условно, на какой либо алгоритм? если да, то пусть при 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?.... |
Сообщ.
#6
,
|
|
|
Заметь, что n - тоже условная хрень. Ибо что это - кол-во замен в массиве? А почему другие операции не считаем?
Короче, сложность дает понятие о масштабе сложности, а не о точном его значении. Это поможет оценить, загнется ли твой алгоритм при растущем n, и как быстро. |
Сообщ.
#7
,
|
|
|
Цитата Машина @ Ибо что это - кол-во замен в массиве? хм..я думал, это количество элементов массива, вполне реальная величина... Добавлено Цитата Машина @ Короче, сложность дает понятие о масштабе сложности, а не о точном его значении. ну допустим, но ведь различия могут быть на несколько порядков...логарифм логарифму рознь... ну вроде, я примерно понял, что главное, отражают сложность через логарифм.... |
Сообщ.
#8
,
|
|
|
ОК, имеется в виду, что n*log(n) - примерное кол-во замен в массиве, отсюда вопрос, почему считаем именно их
|
Сообщ.
#9
,
|
|
|
нет, ну понятно, что есть сравнения, перемещения, выделяемая память и все считаться должно в комплексе...
|
Сообщ.
#10
,
|
|
|
Вся концепция 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 раза |
Сообщ.
#11
,
|
|
|
FasterHarder
В записи O(...) константы перед выражением и величина основания логарифма не имеют значения. Посмотри в википедии определение того, что такое O(f(x)). То есть, коротко говоря, O(3*n) и O(100*n) - одно и то же множество функций. Так же как и O(n*log2(n)) и O(n*log3(n)) - одно и то же множество функций. |
Сообщ.
#12
,
|
|
|
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) - неполиномиальные алгоритмы, в порядке ускорения увеличения затрат времени |
Сообщ.
#13
,
|
|
|
всем пасибо за участие, многое стал понимать лучше...
|