f (n) = log (n)^m - O (n) для всех натуральных чисел m?

Question

TA сказал мне, что это правда сегодня, но я не смог проверить это по поиску в Google. Это такие функции, как log (n)^2, log (n)^3, ..., log (n)^m - все O (n).

Это правда?

Answer 1

претензии

Функция f(n) = log(n)^m, для любого натурального числа m > 2 (m ∈ ℕ+) находится в O(n).

I.e. существует множество положительных констант c и n0 таким образом, что имеет место следующее:

log(n)^m < c · n, for all n > n0, { m > 2 | m ∈ ℕ+ }  (+) 

---

Доказательство

• Предположим, что (+) делает не владение и обозначают это предположение как (*).

Т.е., учитывая (*), не существует множество положительных констант c и n0 таким образом, что (+) имеет место для любого значения m > 2. В соответствии с этим предположением, справедливо следующее, что для всех положительных констант c и n0 существует n > n0 такое, что (спасибо @Oriol):

log(n)^m ≥ c · n, { m > 2 | m ∈ ℕ+ }      (++) 

Теперь, если (++) выполняется, то неравенство в (++) будет сохраняются также после применения любой монотонно возрастающей функции к обеим частям неравенства. Одной из таких функций является, удобно, сама log функция

Таким образом, в предположении, что (++) выполнено, то, для всех положительных констант c и n0, существует n > n0 таким образом, что имеет место следующее

log(log(n)^m) ≥ log(c · n), { m > 2 | m ∈ ℕ+ } 

m · log(log(n)) ≥ log(c · n), { m > 2 | m ∈ ℕ+ }   (+++) 

Однако (+++) очевидно противоречие: с log(n) доминирует (рост WRT) над log(log(n)),

мы можем, для любого заданного значения m > 2 -Всегда найти набор констант c и n0 таким образом, что (+++) (и, следовательно, (++)) нарушается для всех n > n0.

Следовательно, допущение (*) доказано ложно от противоречия, и, следовательно, (+) имеет место.

=> для f(n) = log(n)^m, для любого конечного целого числа m > 2, что оно выполнено f ∈ O(n).

Answer 2

Да. Если функция f(n), это означает, что m является параметром, и f не зависит от него. Фактически, у нас есть другая функция f_m для каждого m.

f_m(n) = log(n)^m 

Тогда это легко. Учитывая m ∈ ℕ, используйте L'Hôpital's rule repeatively

 f_m(n)   log(n)^m   m * log(n)^(m-1) 
limsup ──────── = limsup ────────── = limsup ────────────────── = 
n→∞  n  n→∞  n   n→∞   n 

      m*(m-1) * log(n)^(m-2)    m! 
= limsup ──────────────────────── = … = limsup ──── = 0 
       n      n→∞ n 

Поэтому f_m ∈ O(n).

Конечно, было бы иначе, если бы у нас было f(m,n) = log(n)^m. Например, принимая m=n,

 f(n,n)   log(n)^n 
limsup ──────── = limsup ────────── = ∞ 
n→∞  n  n→∞  n 

Тогда f ∉ O(n)

Answer 3

Во многих отношениях это более интуитивным, что для любого натурального числа m мы имеем:

x^m = O(e^x) 

Это говорит о том, что экспоненциальный рост доминирует полиномиальный рост (поэтому алгоритмы экспоненциального времени являются плохими новостями в компьютерном программировании).

Предполагая, что это правда, просто взять x = log(n) и использовать тот факт, что тогда x стремится к бесконечности, если и только если n стремится к бесконечности, и что e^x и log(x) обратно:

log(n)^m = O(e^log(n)) = O(n) 

Наконец, так как для любое натуральное число m, функция корня n => n^(1/m) увеличивается, можно переписать результат как

log(n) = O(n^(1/m)) 

T его способ написания говорит о том, что log(n) растет медленнее, чем любой корень (квадрат, куб и т. д.) n, что, очевидно, соответствует e^n, растущему быстрее любой степени n.

---

На Edit: выше показал, что log(n)^m = O(n) следовало из более привычной x^m = O(e^x). Чтобы преобразовать его в более самодостаточное доказательство, мы можем показать позже несколько напрямую.

Начнем с ряда Тейлора для e^x:

e^x = 1 + x/1! + x^2/2! + x^3/3! + ... + x^n/n! + ... 

Это, как известно, сходятся для всех действительных чисел x. Если задано положительное целое число m, дайте K = (m+1)!.Тогда, если x > K мы имеем 1/x < 1/(m+1)!, следовательно

x^m = x^(m+1)/x < x^(m+1)/(m+1)! < e^x 

который подразумевает x^m = O(e^x). (Последнее неравенство в приведенном выше случае верно, поскольку все члены разложения для e^x являются строго положительными, если x>0 и x^(m+1)/(m+1)! - это лишь одно из этих условий.)