Java 数据结构 - 渐进符号

算法的渐进分析是指定义其运行时性能的数学边界/框架。使用渐进分析，我们可以很好地得出算法的最佳情况、平均情况和最坏情况。

渐进分析是输入约束的，即如果算法没有输入，则认为它在恒定时间内工作。除了“输入”之外，所有其他因素都被认为是恒定的。

渐进分析是指用计算的数学单位计算任何操作的运行时间。例如，一个操作的运行时间计算为 f(n)，另一个操作的运行时间计算为 g(n²)。这意味着第一个操作的运行时间将随着 n 的增加而线性增加，而第二个操作的运行时间将随着 n 的增加而呈指数增加。同样，如果 n 非常小，则两个操作的运行时间几乎相同。

通常，算法所需的时间分为三种类型：

• 最佳情况 - 程序执行所需的最小时间。

• 平均情况 - 程序执行所需的平均时间。

• 最坏情况 - 程序执行所需的最多时间。

渐进符号

以下是常用的渐进符号，用于计算算法的运行时间复杂度。

• Ο 符号

• Ω 符号

• θ 符号

大O符号，Ο

符号 Ο(n) 是表示算法运行时间上界的正式方法。它衡量最坏情况时间复杂度或算法完成所需的最长时间。

例如，对于函数 f(n)

Ο(f(n)) = { g(n) : 存在 c > 0 和 n0 使得对于所有 n > n0，f(n) ≤ c.g(n)。}

欧米茄符号，Ω

符号 Ω(n) 是表示算法运行时间下界的正式方法。它衡量最佳情况时间复杂度或算法完成所需的最短时间。

例如，对于函数 f(n)

Ω(f(n)) ≥ { g(n) : 存在 c > 0 和 n0 使得对于所有 n > n0，g(n) ≤ c.f(n)。}

西塔符号，θ

符号 θ(n) 是表示算法运行时间上下界的正式方法。它表示如下：

θ(f(n)) = { g(n) 当且仅当 g(n) = Ο(f(n)) 且 g(n) = Ω(f(n)) 对于所有 n > n0。}

常见的渐进符号

以下是一些常见的渐进符号列表：