Большая сложность O в алгоритмах

Question

Я хочу заказать такие термины, что каждый из них является большой-O следующего одного

√n√logn

√n log⁡ (п^30)

п/〖(LOGN)〗^2

〖16〗^(log√n)

Может кто-нибудь помочь в поиске заказ?

Answer 1

Я предполагаю, что вы имеете в виду следующие четыре функции:

1. (n*log(n))^(1/2)
2. n^(1/2)*log⁡(n^30) = 30*n^(1/2)*log(n)
3. n/log(n)^2
4. 16*log(n^(1/2)) = 8*log(n)

и вы хотите понять, почему 8*log(n) = O(n/log(n)^2).

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

---

Наглядно, вы можете начать, показывая, что log(n) = O(n^(1/k)) для любой постоянной k>0. Это также означает, что log(n)^2 = O(n^(1/k)), так как возведение в квадрат обеих сторон неравенства log n < n^(1/k) дает log(n)^2 < n^(2/k), а 2/k по-прежнему является константой.

Далее рассмотрим равенство n^(1/2) == n/n^(1/2). Что произойдет, если вы используете меньший корень, скажем, корень куба? С левой стороны у вас есть функция, которая растет медленнее. Справа, отношение растет больше быстро, потому что вы делите что-то «меньше», так что достаточно большой n, n^(1/3) < n/n^(1/3).Это справедливо для больших констант k, так что в целом n^(1/k) = O(n/n^(1/k)

Наконец, мы сделаем немного handwaving и обратите внимание, что с log(n)^2 растет еще болеемедленнее, чем любой корень, вы можете сказать следующее:

log(n)^2 = O(n^(1/k)) = O(n/n^(1/k)) = O(n/log(n)^2) 

Умножив все константой 8 не будет влиять на вышеуказанную цепь, таким образом, мы можем, наконец, заключить (нестрого), что

8*log(n)^2 = O(n/log(n)^2) 

Answer 2

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

1) предел (№ 2/№1) = (должна быть бесконечность)

2) предел (№ 3/№2) = (должен быть бесконечности)

3) предел (№ 4/№3) = (должно быть бесконечность)

где № I - I-го выражение

Answer 3

претензии: 16*log(sqrt(n)) в O(n/(log(n))^2).

По определению из Wikipedia, f(x) в O(g(x)) тогда и только тогда lim sup abs(f(x)/g(x)) < infinity для п приближающегося бесконечности. Если существует предел Нт вир становится Нт, и используя правило Лопиталя (предполагается, что предварительные условия выполнены, см Wikiepdia), мы имеем:

lim abs(f(x)/g(x)) = lim ((8*log(n))/n) * log(n) * log(n) 
= lim (8*(log(n))^3)/n = lim (24*(log(n))^2)/n 
= lim (48*log(n))/(n^2) = lim (24/n^3) = 0 

Здесь я применил правило l'Hopstial три чтобы избавиться от (log (n))^3. Следовательно, lim существует и, таким образом, равно lim sup и, по определению, следует утверждение.

Answer 4

Интуиция, стоящая за n, превышающая log n, довольно ясна, так что давайте будем говорить об этом строго.

limit n->infinity (16 log(sqrt(n))/(n/(log n)^2) 
= limit n->infinity 8 (log n)^3/n = 0 

Если мы докажем последнее равенство, порядок следует. Мы можем использовать правило l'Hospital «S несколько раз, чтобы получить:

limit n->infinity 8 (log n)^3/n 
= limit n->infinity 24 (log n)^2/n 
= limit n->infinity 48 (log n)/n 
= limit n->infinity 48/n = 0