时间和空间复杂度

时间复杂度和空间复杂度分别用来衡量程序在运行中随着数据规模增长带来的时间和空间上的变化，所以其实全称应该叫做渐进时间复杂度和渐进空间复杂的。

为什么要学习时间和空间复杂度，通过代码或者其他工具不能衡量程序性能吗？

通过代码中埋点或者一些测试、运维、性能监控工具当然能够衡量程序消耗的时间和空间，而且还比时间空间复杂的更加的精确，但是这种方式也有其局限性。

很好理解，同样的代码，在不同配置的服务器上性能是完全不一样的。这样的话，可能我们写的代码在公司自己的服务器跑的飞起，结果部署到客户方直接就内存泄漏了。

同样的代码，同样的算法，在不同的数据规模下的表现可能大相径庭。而且如果数据量非常之大，跑一遍代码的代价就非常大了，可能花我几个小时的时间。

其中比较复杂的可能就是对数阶时间复杂度了，可以参考以下推导文章：
等比数列公式推导

这个很好理解，比如在一个循环中，当满足某个条件的时候就退出循环。这种情况最理想的就是，循环第一次的时候满足条件退出，时间复杂度为O(1)，而最不理想的情况就是循环到最后一个都没有满足条件的，时间复杂度为O(n)。

平均时间复杂度和均摊时间复杂度很像，实际上可以说均摊时间复杂度就是一种特殊的平均时间复杂度。