算法效率中的基本概念

2024备考建议

算法复杂度是一个必考的知识点，常常出现在阅读程序题中，让考生进行判断。

1.先理解算法模板的复杂度计算

2.再尝试套用初赛题目中的复杂度计算

3.递归算法的复杂度可以展开计算

算法效率是评估算法性能的一个关键指标，一般而言分析算法效率的方式有两种:

1. 时间复杂度
2. 空间复杂度

在一般的算法分析中，考察的主要是时间复杂度。

基本操作数

算法的运行速度受计算机性能的影响，所以通常考虑算法效率的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。

像加减乘除、访问变量、给变量赋值等都可以看作基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标。

时间复杂度

在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即 ​时间复杂度​。

变化趋势意味着我们不用纠结于具体的操作次数和n之间的精确对应关系，也就是不用看具体的函数的参数是什么，而只用看随着数据范围的增大，操作次数的变化是属于哪一类函数。