Является ли сложность O (log (n)) эквивалентной O (sqrt (n))?

Мой профессор просто научил нас, что любая операция, которая уменьшает длину ввода, имеет сложность O (log (n)) как правило большого пальца. Почему это не O (sqrt (n)), оба они не эквивалентны?

Ответ 1

Они не эквивалентны: sqrt (N) будет увеличиваться намного больше, чем log ₂ (N). Нет константы C, так что у вас будет sqrt (N) < C.log(N) для всех значений N больше некоторого минимального значения.

Легким способом захвата этого является то, что log ₂ (N) будет значением, близким к числу (двоичных) цифр N, тогда как sqrt (N) будет числом, которое имеет половину числа цифр, которое имеет N. Или, чтобы утверждать, что с равенством:

log ₂ (N) = 2log ₂ (sqrt (N))

Итак, вам нужно взять логарифм (!) sqrt (N), чтобы привести его к тому же порядку сложности, что и log ₂ (N).

Например, для двоичного числа с 11 цифрами, 0b10000000000 (= 2 ¹⁰), квадратный корень равен 0b100000, но логарифм равен всего 10.

Ответ 2

Предполагая 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 для альтернативного определения O(.) и, следовательно, сверху мы можем сказать log n = O(sqrt(n)),

Также сравните рост функций ниже, log n всегда ограничен сверху sqrt(n) для большого n.

Ответ 3

Нет, это не эквивалентно.

@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

Ответ 4

Нет, они не эквивалентны; вы даже можете доказать, что

   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 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))

Ответ 5

Нет, это не так. Когда мы имеем дело со сложностью времени, мы думаем о входе как об очень большом количестве. итак, пусть n = 2 ^ 18. Теперь для sqrt (n) число операций будет 2 ^ 9, а для log (n) оно будет равно 18 (здесь мы рассмотрим log с базой 2). Очевидно, что 2 ^ 9 намного больше, чем 18. Таким образом, мы можем сказать, что O (log n) меньше, чем O (sqrt n).