big-o - (log 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如果存在正常数 N 和 c，则函数在 O(g(n)) 中，因此对于所有n > N: f(n) <= c*g(n)。在这种情况下f(n)is(log n)^k和g(n)is 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 规则相对简单.. 但是它可以在没有微积分的情况下完成。

---

我能想出的最简单的证明不依赖于 L'Hopitals 规则使用泰勒级数

e^z = 1 + z + z^2/2 + ... = sum z^m / m!

使用z = (N! x)^(1/N)我们可以看到

e^(x^(1/N)) = 1 + (N! x)^(1/N) + (N! x)^(2/N)/2 + ... (N! x)^(N/N)/N! + ...

对于 x>0，所有项都是正数，所以只保留第 N 个项，我们得到

e^((N! x)^(1/N)) = N! x / N! + (...) 
                 = x + (...)
                 > x  for x > 0

取两边的对数（因为log是单调递增的），然后升到N次方（也是单调递增，因为N>0）

(N! x)^(1/N) > log x  for x > 0
N! x > (log x)^n      for x > 0

这正是我们需要的结果，(log x)^N < M x对于 someM和 all x > x_0，使用M = N!andx_0=0