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 的定义是，如果存在正常数 N 和 c，则函数 f 在 O(g(n)) 中，对于所有 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) 中。

how can a function f(x) have a run time complexity

它没有。 big-Oh 表示法没有任何特定于运行时复杂性的内容。 Big-Oh 是一种对函数增长进行分类的符号。通常我们谈论的函数测量某些算法的运行时间，但我们可以使用 big-Oh 来谈论任意函数。