在编程世界中,我们经常面临这样的选择:用哪种算法解决问题更好?当数据量很小的时候,各种算法可能差别不大。但当数据规模达到百万、千万级别时,不同算法的效率差异就会变得天壤之别。这就是时间复杂度概念如此重要的原因。在接触STL时,掌握时间复杂度这个概念有利于提高我们的算法素养。

时间复杂度,我们一般用O(大写字母o)表示。我们常常看到O(n),这里n指的是操作元素的个数,一般有大O表示法有以下四种:

复杂度类型

增长特点

代码

典型场景

O(1) 常数时间

时间与数据量无关

arr[0]

数组索引、哈希查找

O(log n) 对数时间

数据翻倍,操作+1

二分查找

二分搜索、平衡树

O(n) 线性时间

数据翻倍,时间翻倍

遍历数组

线性搜索、列表遍历

O(n²) 平方时间

数据翻倍,时间4倍

嵌套循环

冒泡排序、简单矩阵运算

大O表示法关注的是算法随数据规模增长的长期趋势,而非具体执行时间。它会忽略常数因子和低阶项,因此100n和2n都被视为O(n)。这种方法在数据量很大时非常有效,能清晰区分不同算法的 scalability。但需要注意,当处理小规模数据时,常数因子可能起决定性作用,此时理论复杂度最优的算法未必是实际最快的选择。

掌握了这个大O表示法,你就能真正理解为什么STL中有些算法在处理大数据时依然高效,而有些算法则应该避免使用。这是成为优秀程序员的必修课!

点赞(1)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

Dotcpp在线编译      (登录可减少运行等待时间)