Что выбрать, чтобы выбрать большой ой нотации

Question

Что такое Большой о n ^ 2 + nlog (n)?докажи свой ответ.Как выбрать большую ой нотацию: n ^ 2 или nlog (n), какую стратегию выбрать?

и если я выберу nlog (n), как мне это решить?

Answer 1

Вы, кажется, знаете, что когда вы суммируете две функции, Big O - это Big O "большей" функции (для произвольно большого n), поэтому нам просто нужно найти, какая из двух функций это.Чтобы сделать это, мы можем решить следующий предел:

  lim (n -> inf) n^2 / nlog(n)
= lim (n -> inf) n / log(n)
= lim (n -> inf) 1 / (1 / n) (L'Hopital's Rule)
= inf

Это доказывает, что n ^ 2 является «большей» функцией, и поэтому O (n ^ 2 + nlog (n)) = n ^ 2

Обратите внимание, что вы также могли показать, что:

lim (n -> inf) nlog(n) / n^2 = 0