渐近分析:大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)
被认为是渐近紧密界。
想正确学习时间复杂度吗? 免费报名我们的 交互式复杂度计算课程。