【数据结构与算法 | 第一篇】时间复杂度和空间复杂度

前言

学习数据结构与算法，先要分清两个问题：数据怎样组织，操作怎样完成。前者由数据结构解决，后者由算法解决。写代码时，除了得到正确结果，还要关注程序执行要花多少时间、占多少额外空间。

数据结构和算法是什么

数据结构是数据在计算机中的组织方式。它既包含数据之间的逻辑关系，也包含具体的存储方式。

从逻辑结构看，常见的类型有集合结构、线性结构、树形结构和图状结构。例如数组和链表属于线性结构，二叉树属于树形结构。

从存储方式看，数据可以连续存放，也可以离散存放：

• 顺序存储：元素放在连续的存储空间中，例如数组。
• 非顺序存储：元素分散存放，通过关系把它们连接起来，包括链式存储、索引存储和散列存储。

算法是解决某类问题的一组有限步骤。一个算法需要具备确定性：相同的输入应得到相同的输出；它也必须在有限步骤后结束。评价算法时，除了正确性、可读性和健壮性，还要看运行效率和存储需求。

时间复杂度

时间复杂度用来描述：当数据规模 n 增大时，算法执行次数增长得有多快。它通常写成O( )，关注增长趋势，不统计某一台电脑上的实际秒数。

计算规则

多项式相加，只保留最高阶，系数化为 1。

例如：

T(n) = 3n² + 5n + 10

当 n 很大时，n² 的增长最快，因此时间复杂度为O(n²)。

嵌套循环，复杂度相乘。

for(inti=0;i<n;i++){for(intj=0;j<n;j++){// 执行一次常量操作}}

外层循环执行 n 次，内层每次执行 n 次，总执行次数约为 n × n，所以时间复杂度是O(n²)。

顺序执行的代码，复杂度相加后再取最高阶。

for(inti=0;i<n;i++){// O(n)}for(intj=0;j<n*n;j++){// O(n²)}

总复杂度为 O(n + n²)，保留最高阶后是O(n²)。

常见时间复杂度从低到高可以简单记为：O(1)、O(log n)、O(n)、O(n log n)、O(n²)。在数据量较大时，增长级别的差异会非常明显。

空间复杂度

空间复杂度描述算法运行时额外申请的存储空间随 n 的增长情况。这里主要看辅助变量、数组、递归调用等产生的额外空间，不把输入数据本身重复计算进去。

计算规则

固定数量的变量，占用常量空间。

intmax=0;intindex=0;

无论 n 多大，变量数量都不变，空间复杂度为O(1)。

申请长度和 n 成正比的数组，空间复杂度为 O(n)。

int[]temp=newint[n];

数组长度随 n 一起增长，因此额外空间为O(n)。

二维数组的行和列都与 n 有关，空间复杂度为 O(n²)。

int[][]matrix=newint[n][n];

它一共保存 n × n 个元素，因此空间复杂度为O(n²)。

循环次数多不一定占用更多空间。只要循环中没有持续申请与 n 相关的新空间，即使时间复杂度是 O(n²)，空间复杂度也可能仍是 O(1)。

总结

数据结构决定数据怎样存放，算法决定问题怎样求解。分析复杂度时，时间复杂度看操作次数的增长，空间复杂度看额外存储量的增长。掌握“取最高阶”和“嵌套相乘”这两条规则，就能完成大多数基础复杂度判断。