C&C++
发布时间:2022-04-03 发布网站:大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了算法复杂度的衡量标准:大O表示法,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
学习
C++ 标准库,特别是
STL,经常需要
考量算法和成员
函数的效能(也就是运行效率,又称
复杂度),因此每个学习 STL 的读者都需要掌握一种衡量算法(或成员
函数)复杂度的
方法,目前最常用的
方法称为
大 O 表示法(注意,不是数字 0,而是字母 O)。
使用大 O 表示法衡量某个算法的复杂度,其实就是将该算法的运行时间用输入量为 n 的
函数表示出来。这里的输入量 n 在 STL 中通常指的是算法操作的元素个数。
举个例子,当算法运行时间随元素个数成线性增长时(即如果元素个数呈倍数增长,运行时间也呈倍数增长),该算法的复杂度用 O(n) 来表示;反之,如果算法的运行时间和输入量 n 无关,则该算法的复杂度就用 O
(1) 来表示。
表 1 列出了常见的算法复杂度种类,以及使用大 O 表示法表示的复杂度。
表 1 常见的算法复杂度表示
算法复杂度种类 |
含义 |
大 O 表示法 |
常数阶 |
算法运行时间和所操作的元素个数无关 |
O(1) |
对数阶 |
算法运行时间随所操作的元素个数呈对数增长 |
O(log(n)) |
线性阶 |
算法运行时间随所操作的元素个数呈线性增长 |
O(n) |
指数阶(m次方,m为数字) |
算法运行时间随所操作的元素个数呈 m 次方增长 O(n@H_998_52@m) |
常见的有 O(n2)、O(n3) 等 |
值得注意的是,大 O 表示法并不关心算法运行所消耗的具体时间,换句话说,对于那些影响算法运行效率较小的因素,使用大 O 表示法表示时会直接将其忽略。例如,某个算法运行的复杂度为 O(n),呈线性增长,但至于线性增长的具体程度(是 100n 还是 2n),在大 O 表示法看来,它们是一样的。也就是说,采用这种测量法则,任何两个线性算法都将被视为具
有相同的复杂度。
所以请读者记住,大 O 表示法只是某种度量
方法,它所
显示的算法的最佳复杂度,并不一定就是真正的最佳(最快)算法。
表 2 复杂度随元素个数对照表
复杂度 |
元素个数 |
种类 |
大 O 表示 |
1 |
2 |
5 |
10 |
50 |
100 |
1 000 |
10 000 |
常量阶 |
O(1) |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
对数阶 |
O(log(n)) |
1 |
2 |
3 |
4 |
6 |
7 |
10 |
13 |
线性阶 |
O(n) |
1 |
2 |
5 |
10 |
50 |
100 |
1 000 |
10 000 |
2次方 |
O(n2) |
1 |
4 |
25 |
100 |
2500 |
10 000 |
1 000 000 |
100 000 000 |
表 2 列出了常用的复杂度随元素个数增长的变化程序。可以看到,当算法处理的元素较少时,各复杂度的差别很小,此时算法效率的优劣往往受被大 O 表示法忽略部分的影响更大。而当处理元素个数越多,各复杂度的差别越大,此时复杂度被忽略的部分就变得无关紧要了。
因此,在
考量算法的复杂度时,输入量 n (操作元素的个数)的值必须足够大才有意义。
大佬总结
以上是大佬教程为你收集整理的算法复杂度的衡量标准:大O表示法全部内容,希望文章能够帮你解决算法复杂度的衡量标准:大O表示法所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。