(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在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来讨论任意函数.

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对于某些M和所有x > x_0，M = N!和x_0=0