(журнал n) ^ k = O (n)?Для k больше или равно 1

Question

(log n)^k = O(n)? For k greater or equal to 1.

Мой профессор представил нам это утверждение в классе, однако я не уверен, что означает, что функция имеет временную сложность O (n).Даже такие вещи, как n^2 = O(n^2), как функция f (x) может иметь сложность во время выполнения?

Что касается утверждения, как оно равно O (n), а не O ((logn) ^ k)?

Answer 1

(log n) ^ k = O (n)?

Да. Определение big-Oh состоит в том, что функция f находится в O (g (n)), если существуют положительные константы N и c, такие что для всех n > N: f(n) <= c*g(n). В этом случае f(n) равно (log n)^k и g(n) равно n, поэтому, если мы вставим это в определение, мы получим: «существуют константы N и c, такие что для всех n > N: (log n)^k <= c*n» , Это верно, поэтому (log n)^k в O (n).

как может функция f (x) иметь сложность во время выполнения

Это не так. Ничто в нотации big-Oh не относится к сложности времени выполнения. Big-Oh - это обозначение для классификации роста функций. Часто функции, о которых мы говорим, измеряют время выполнения определенных алгоритмов, но мы можем использовать big-Oh, чтобы говорить о произвольных функциях.

Answer 2

f(x) = O(g(x)) означает, что f(x) растет медленнее или сравнимо с g(x).

Технически это интерпретируется как "Мы можем найти значение x x_0 и коэффициент масштабирования M, так что этот размер f(x) мимо x_0 меньше масштабированного размера g(x) «. Или по математике:

|f(x)| < M |g(x)| for all x > x_0.

Итак, на ваш вопрос:

log(x)^k = O(x)? спрашивает: есть ли x_0 и M такие, что log(x)^k < M x for all x>x_0.

Существование таких M и x_0 может быть сделано с использованием различных предельных результатов и относительно просто с использованием правила L'Hopitals ... однако, возможно, где-то есть хорошее доказательство без исчисления где-то ...