Мой профессор просто научил нас, что любая операция, которая уменьшает длину ввода, имеет сложность O (log (n)) как правило большого пальца. Почему это не O (sqrt (n)), оба они не эквивалентны?Является ли сложность O (log (n)) эквивалентной O (sqrt (n))?
Они не эквивалентны: SQRT (N) увеличится намного больше, чем журнал (N). Нет постоянной C, так что у вас было бы sqrt (N) < C.log (N) для всех значений N больше некоторого минимального значения.
простой способ, чтобы захватить это, является то, что журнал (N) будет значение, близкое к числу (двоичных) цифр N, в то время как SQRT (N) будет число, которое имеет половину числа цифр, которое N имеет. Или, чтобы утверждать, что с равенством:
журнал (N) = 2log (SQRT (N))
Так что вам нужно взять логарифм (!) sqrt (N), чтобы свести его к тому же порядку сложности, что и log (N).
Например, для двоичного числа с 11 цифр, 0b10000000000 (= 2), квадратный корень 0b100000, но логарифм только 10.
+1 для 'log (N) будет значением, близким к числу (двоичных) цифр N, тогда как sqrt (N) будет числом, которое имеет половину числа цифр, которое имеет N.' –
Нет, это не эквивалентны.
@ trincot дал одно превосходное объяснение с примером в его ответе. Я добавляю еще один момент.Ваш профессор учил вас, что
any operation that halves the length of the input has an O(log(n)) complexity
Это также верно, что,
any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity
So on ...
Это верно даже для всех уменьшения длины входа по (B-1)/Bth. Затем имеет сложность O(logB(n))
N:B:O(logB(n)) означает B на основе логарифма от n
Предполагая natural logarithm (в противном случае просто умножить на константу), мы имеем
lim {n->inf} log n/sqrt(n) = (inf/inf)
= lim {n->inf} 1/n/1/(2*sqrt(n)) (by L'Hospital)
= lim {n->inf} 2*sqrt(n)/n
= lim {n->inf} 2/sqrt(n)
= 0 < inf
Обратитесь к https://en.wikipedia.org/wiki/Big_O_notation альтернативной Defination из O(.) и, таким образом, из вышесказанного можно сказать, log n = O(sqrt(n)),
Также сравнить Рост f функции ниже, log n всегда верхний ограничен sqrt(n) для больших n.
Нет, они не эквивалентны; Вы можете даже доказать, что
O(n**k) > O(log(n, base))
для любого k > 0 и base > 1 (k = 1/2 в случае sqrt).
Когда мы говорим о O(f(n)) мы хотим исследовать поведение для большихn, пределов является хорошим средством для этого. Предположим, что оба большие O эквивалентны:
O(n**k) = O(log(n, base))
, который означает, что есть некоторая конечная константа C такая, что
O(n**k) <= C * O(log(n, base))
начиная с некоторого достаточно n большой; положить его в других условиях (log(n, base) не 0 начиная с большого n, обе функции непрерывно дифференцируемы):
lim(n**k/log(n, base)) = C
n->+inf
Чтобы узнать значение этого лимита мы можем использовать L'Hospital's Rule, т.е. взять производные для числитель и знаменатель и разделить их :
lim(n**k/log(n)) =
lim([k*n**(k-1)]/[ln(base)/n]) =
ln(base) * k * lim(n**k) = +infinity
поэтому мы можем заключить, что нет ни одного постоянного C таким образом, что O(n**k) < C*log(n, base) или другими словами
O(n**k) > O(log(n, base))
Постройте графики 'log (n)' и 'sqrt (n)' примерно до 'n == 1000', посмотрите, считаете ли вы, что они эквивалентны, что бы вы ни подразумевали под этим. –
log (1) = 0 и sqrt (1) = 1 – Sung
Извините, я не знаю, что я думал, все ответы чрезвычайно информативны. Спасибо –