渐近分析：大O符号等
- 渐近符号的概念：渐近符号用于描述算法随输入大小变化时的运行时间，包括大O符号、Omega符号和Theta符号。
- 大O符号（O-符号）：表示算法运行时间的上界，即最坏情况复杂度，常用于分析算法的最坏性能。
- Omega和Theta符号：Omega符号表示算法运行时间的下界（最佳情况复杂度），而Theta符号则同时表示上界和下界，用于分析算法的平均情况复杂度。
算法的效率取决于执行算法所需的时间、存储和其他资源的数量。这种效率是通过渐进符号来衡量的。
算法对不同类型的输入可能有不同的性能。随着输入大小的增加，性能会发生变化。
算法性能随输入大小的顺序变化而变化的研究被定义为渐进分析。
想要正确学习时间复杂度吗？ 免费报名参加我们的交互式复杂度计算课程。
渐进符号
渐进符号是用来描述算法运行时间的数学符号，当输入趋向于特定值或极限值时。
例如：在冒泡排序中，当输入数组已经排序时，算法所需的时间是线性的，即最佳情况。
但是，当输入数组处于逆序状态时，算法需要最大的时间（二次方）来排序元素，即最差情况。
当输入数组既不是排序的也不是逆序的，那么它需要平均时间。这些持续时间使用渐进符号表示。
主要有三种渐进符号：
- 大O符号
- Omega符号
- Theta符号
大O符号（O-符号）
大O符号表示算法运行时间的上界。因此，它给出了算法的最差情况复杂度。
O(g(n)) = { f(n): 存在正常数 c 和 n0
使得 0 ≤ f(n) ≤ cg(n) 对所有 n ≥ n0 }
上述表达式可以描述为一个函数 f(n) 属于集合 O(g(n))，如果存在一个正常数 c，使其介于 0 和 cg(n) 之间，对于足够大的 n。对于任何值的 n，算法的运行时间不会超过 O(g(n)) 提供的时间。
由于它给出了算法的最坏情况运行时间，因此广泛用于分析算法，因为我们总是对最坏情况感兴趣。
Omega 符号（Ω-符号）
Omega 符号代表算法运行时间的下界。因此，它提供了算法的最佳情况复杂度。
Ω(g(n)) = { f(n): 存在正常数 c 和 n0，
使得对所有 n ≥ n0，有 0 ≤ cg(n) ≤ f(n) }
上述表达式可以描述为：如果存在一个正常数 c 使得对于足够大的 n，f(n) 位于 cg(n) 之上，则函数 f(n) 属于集合 Ω(g(n))。
对于任何值的 n，算法所需的最小时间由 Omega Ω(g(n)) 给出。
Theta 符号（Θ-符号）
Theta 符号从上下两端封闭函数。由于它代表了算法运行时间的上界和下界，因此用于分析算法的平均情况复杂度。
对于函数 g(n)，Θ(g(n)) 由以下关系给出：
Θ(g(n)) = { f(n): 存在正常数 c1、c2 和 n0，
使得对所有 n ≥ n0，有 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) }
上述表达式可以描述为：如果存在正常数 c1 和 c2 使得对于足够大的 n，f(n) 可以夹在 c1g(n) 和 c2g(n) 之间，则函数 f(n) 属于集合 Θ(g(n))。
如果对于所有 n ≥ n0，函数 f(n) 位于 c1g(n) 和 c2g(n) 之间的任何位置，则 f(n) 被认为是渐近紧密界。
想正确学习时间复杂度吗？ 免费报名我们的 交互式复杂度计算课程。