Найти биг-О функции

Question

Пожалуйста, помогите мне с выполнением следующих двух функций, мне нужно их упростить.

O (nlogn + n ^ 1.01)

O (log (n ^ 2))

Моя текущая идея

O (nlogn + n ^ 1.01) = O (nlogn)

O (log (n ^ 2)) = O (log (n ^ 2))

Пожалуйста, помогите мне решить эти две проблемы упрощения и кратко объясните, спасибо.

Answer 1

Во-вторых, у вас есть O (lg (n²)) = O (2lg (n)) = O (lg (n)).

Во-первых, у вас есть O (nlg (n) + n ^ (1.01)) = O (n (lg (n) + n ^ (0.01)), вы должны решить, какой lg (n) или n ^ (0,01) становится больше.

Для этой цели вы можете взять производную от n ^ 0,01 - lg (n) и посмотреть, является ли она положительной или отрицательной при пределе n -> бесконечности: 0,01 / x ^ (0,99) - 1 / Икс; на пределе x больше, чем x ^ 0,99, поэтому разница положительна и, следовательно, n ^ 0,01 растет асимптотически быстрее, чем log (n), поэтому сложность составляет O (n ^ 1,01).

Answer 2

Помните:

log (x * y) = log x + log y

и n^k всегда растут быстрее, чем log n для любого k>0.

Answer 3

Собирая все вместе, для первого вопроса O(n*log(n)+n^1.01) первая функция растет быстрее, чем второе слагаемое, т. Е. Поскольку n<em>log(n) > n^1.01 для n больше, чем примерно 3, это O(n</em>log(n))

Во втором случае используйте формулу, упомянутую KennyTM, поэтому мы получаем

O(log(n^2)) = O(log(n*n)) = O(log(n)+log(n)) = O(2*log(n)) = O(log(n))

потому что постоянные члены можно игнорировать.