大家好，欢迎来到IT知识分享网。
复杂度度量
1.时间复杂度
特定算法处理规模为n的问题所需要的时间可记作T(n)，严格来说这个定义并不明确。为此需要做进一步简化，即从保守估计的角度出发，在规模为n的所有输入中选择执行时间最长者作为T(n),并以T(n)度量该算法的时间复杂度。
2.渐进复杂度
着重长远、更为注重时间复杂度的总体变化趋势和增长速度的策略与方法，即所谓的渐进分析（asymptotic analysis）。那么，针对足够大的输入规模n，算法执行时间T(n)的渐进增长速度应该如何评价和度量？引入以下几个符号。
2.1大O记号（
big-O）
big-O）
出于保守估计，我们首先关注T(n)的渐进上届。为此可引入所谓“大O记号”（
big-O）。具体地，若存在正的常数c和函数f(n)，使得对任何n>>2都有
big-O）。具体地，若存在正的常数c和函数f(n)，使得对任何n>>2都有
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819110306096 "2.算法复杂度度量[亲测有效]插图")
![2.算法复杂度度量[亲测有效]](https://yundeesoft.com/wp-content/uploads/2022/11/2022112316405970.jpg "2.算法复杂度度量[亲测有效]插图1")
则可认为在n足够大之后，f(n)给出了T(n)增长速度的一个渐进上界。此时记之为：
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819110901723 "2.算法复杂度度量[亲测有效]插图2")
由这一定义，可以导出大O记号的以下性质：
(1)对于任一常数c>0，有
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819111207089 "2.算法复杂度度量[亲测有效]插图4")
(2)对于任意常数a>b>0，有
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819111543410 "2.算法复杂度度量[亲测有效]插图6")
“最坏情况复杂度”是人们关注且使用最多的。
2.2大Ω记号（
big-Omega）
big-Omega）
为了对算法的最好情况做出估计，需要借助另一个符号。如果存在正的常数c和函数g(n)，使得对于任何n>>2都有
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819112128090 "2.算法复杂度度量[亲测有效]插图8")
就可以认为，在n足够大之后，g(n)给出了T(n)的一个渐进下届。此时我们记之为：
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819112355162 "2.算法复杂度度量[亲测有效]插图10")
这里的Ω称作“大Ω记号”。与大O记号恰恰相反，大Ω记号是对算法执行效率的乐观估计——对于规模为n的任意输入，算法的运行时间都不低于Ω(g(n))。比如在最好的情况下，起泡排序也至少需要T(n)=Ω(n)的计算时间。
2.2大Θ记号（big-Theta）
借助大O记号和大Ω记号可以对算法的时间复杂度做出定量的界定，亦即，从渐进的趋势看，T(n)界于Ω(g(n))和O(f(n))之间。恰巧出现g(n)=f(n)的情况，可以使用另一记号来表示。
如果存在正的常数c1<c2和函数h(n)，使得对于任何n>>2都有
![2.算法复杂度度量[亲测有效]](https://img-blog.csdn.net/20170819113725145 "2.算法复杂度度量[亲测有效]插图12")
就可以认为在n足够大之后，h(n)给出了T(n)的一个确界。此时，我们记之为：
T(n)=Θ(h(n))
这里的Θ称作“大Θ记号”，它是对算法复杂度的准确估计——对于规模为n的任何输入，算法的运行时间T(n)都与Θ(h(n))同阶。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/24324.html
