Какова большая-функция функции (log n) ^ 2 + logn

Ответ 1

Любая функция, время выполнения которой имеет вид (log n) ^k равно O ((log n) ^k). Это выражение не сводится к любой другой примитивной функции с использованием простых преобразований, и довольно распространено видеть алгоритмы с такими же временем выполнения, как O (n (log n) ²). Функции с этой скоростью роста называются полилогарифмическими.

Кстати, обычно (log n) ^k записывается как log ^k n, поэтому приведенный выше алгоритм имел бы время выполнения O (n log ² n. В вашем случае функция log ² n + log n будет O (log ² n).

Однако любая функция со временем выполнения формы log (n ^k) имеет время выполнения O (log n), считая, что k является константой. Это связано с тем, что log (n ^k) = k log n, используя логарифмические тождества, а k log n - O (log n), поскольку k - постоянная. Вы должны быть осторожны, чтобы не слепо заключить, что алгоритм O (log (n ^k)) равен O (log n); если k является параметром функции или зависит от n, то правильным вычислением большого числа будет O (k log n) в этом случае.

В зависимости от контекста, в котором вы работаете, вы иногда видите, что обозначение Õ (f (n)) означает O (f (n) log ^k n) для некоторой константы k. Это иногда называют " soft-O" и используется в контекстах, в которых логарифмические термины не имеют значения. В этом случае вы можете сказать, что обе функции являются Õ (1), хотя это использование не является обычным в простом алгоритмическом анализе (фактически, за пределами Википедии, я видел, что это использовалось точно один раз).

Надеюсь, это поможет!

Ответ 2

log(n) O((log(n))^2), поэтому все выражение O((log(n))^2)

Ответ 3

(log n) ^ k:

• O ((log n) ^ k)
• О (п ^ к)
• О (п)
• O (n log n)
• О (п ^ 1/2)
• О (п ^ 0,00000002)

и т.д.. Какой смысл для вас зависит от констант и контекста.

Ответ 4

Он по-прежнему будет (log(n))^2. Логарифм, поднятый до мощности, уже находится в самой низкой/простейшей форме.