时间复杂度和空间复杂度如何衡量？

本文共计1641个文字，预计阅读时间需要7分钟。

复杂度分析+复杂度分析在我看来是数据结构与算法学习入门的重要知识。为什么复杂度分析重要？因为数据结构与算法的出现本质就是为了解决更少的时间和空间（存储）问题。

复杂度分析

复杂度分析在我看来是数据结构与算法学习入门知识，尤为重要。

为什么复杂度分析重要？

数据结构与算法的出现本就是为了花更少的时间和空间（储存）来解决问题。复杂度分析就是为解决如何“花更少的时间和空间（储存）”的问题。

现在各种编译工具，代码跑完就能显示用了多少时间，占了多少内存。但是这些数据都是在完成代码编写之后才能得到的，这是事后统计方法。

事后统计法得到的结果会因计算机性能和测试数据规模不同而有较大差异。这并不能体现出代码本身的效率、优劣程度，而且很可能写出的代码本身就不太行。。。

而复杂度分析不依赖软硬件性能、数据规模等就能直接估算算法的效率、优劣，这就是其重要性。

时间复杂度

时间复杂度即算法的运行时间。

用运行时间去描述算法的效率时，算法的执行总步数越多算法越慢，总步数越少则越快。

假设每一行代码运行时间都为X，则算法的总运行时间等于运行的总代码行数。

1 def sum(n): 2 sum = 0 3 4 for i in range(n): 5 sum += i 6 return sum

在上面代码中，假设运行一行需要 1t，则第二行运行时间为 1t，第四行、第五行执行了n遍，每行运行时间为 nt，则运行总时间就是（1+2n）t

用函数来表示就是 T(n) = (1+2n) t，可以看出T(n)和总步数成正比关系。