Понимание примера верхней и нижней границ алгоритмического анализа

Question

Я продолжаю свою задачу понимания асимптотического анализа.Лучше всего просто иметь мета-пост, если предпочитают моды.В любом случае:

У меня есть две функции:

 f(n) = n^2
 g(n) = (log n)^80

Из анализа с правилом l'Hopitals:

 lim(n->∞) f(n)/g(n) = f'(n)/g'(n)

Что оставляет нас с нами:

 f'(n)/g'(n) = 2n/(80*(log n / √2)

Что в конечном итоге приведет нас к:

 0/g''(n) = 0 

Что, насколько я понимаю, показывает, что f (n) = o (g (n))

Правильно ли мое понимание?

Answer 1

Вы можете применить правило L'Hopital, если числитель и знаменатель сходятся к нулю или бесконечности.Так что твой подход в целом верен.Но вы сделали ошибку, чтобы вычислить g '(n).

g'(n) = (80 * log(n)) * 1/(2 ln (n))
  => f'(n)/g'(n) = 2n / ((80 * log(n)^79) * 1/(n ln(2))) 
   = 2n^2 / 80log(n)^79 ln(2)

На данный момент предел f '(n) / g' (n) тоже равен ∞ / ∞.Таким образом, вы можете применить правило L'Hopital снова.Но результат тот же.Но после 80-го применения у вас есть это:

2^80 n^2 / 80! ln(2)^80
  =>  lim(n->∞) f(n)/g(n) = ∞ 

Таким образом, g (n) = o (f (n)) .