Big O обозначение O (p ^ 2 log p)

Question

Пожалуйста, помогите мне описать и решить, почему

Θ (p ^ 2 log p ^ 2) = Θ (p ^ 2 log p)

Я действительно ошеломлен этим.

Answer 1

log (p ^ 2) = 2 log p (как правило, log (n ^ m) = m log n )

Поскольку 2 - это просто константа, имеем that (log p ^ 2) = Θ (log p).

Следовательно, мы получаем Θ (p ^ 2 log p ^ 2) = Θ (p ^ 2 log p).

Answer 2

Всегда хорошо начать с определения! Wiki

нотация Big-O описывает ограничение поведение функции, когда аргумент стремится к определенному значение или бесконечность

Ограничивающее поведение одинаково для функций f и g, если g = C*f. Асимптотически они ведут себя одинаково. Теперь к log. Помните формулу:

log _b x ^y = y log _b x

Это означает, что они отличаются только константой, что не меняет ограничивающего поведения.

Но важно помнить, что их скорость и количество операций все еще различны (по константе).

Answer 3

Если x = log p^2, это означает, что e^x = p^2. Это означает, что sqrt(e^x) = p, и так e^(x*1/2) = p. Так что (log p^2)/2 = log p. Это означает, что p^2 log p^2 = 2 p^2 log p; так как это множители константы с большой тэтой, то их можно отбросить, поэтому они получаются эквивалентными.

Answer 4

Полагаю, потому что log (x ^ n) = nlog (x).И n является константой, поэтому не имеет значения в Big O. Другими словами, O (n) = O (2n), потому что они вдвое хуже, когда n удваивается.