algorithm - 数据结构。 f(x) 和 g(x)

Question

我能理解算法中的运行时复杂度。但是，当我们知道算法运行时复杂度为 O(n) 时，有点困惑。

我们可以知道 f(n)< g(n)..

g(n) 究竟是什么……？

抱歉这个菜鸟问题..

谢谢。

Answer 1

设f(x) 和g(x) 是定义在实数的某个子集上的两个函数。一个写

f(x) = O(g(x)) as x -> infinity

当且仅当存在正实数 M 和实数 x0 使得

|f(x)| <= M |g(x)| for all x > x0

一般来说，f(x) 是算法在 x 的输入规模上的实际成本(例如执行步骤数)，而 g( x)比f(x)简单得多，可以用来表征f(x)的复杂行为。