时间复杂度、空间复杂度

算法复杂度分为时间复杂度和空间复杂度。

其作用：

时间复杂度是指执行算法所需要的计算工作量；

而空间复杂度是指执行这个算法所需要的内存空间。

时间复杂度

计算时间复杂度的方法：

用常数1代替运行时间中的所有加法常数

修改后的运行次数函数中，只保留最高阶项

去除最高阶项的系数

按数量级递增排列，常见的时间复杂度有：

常数阶​<code>​O(1)​</code>​,对数阶​<code>​O(log2n)​</code>​,​<code>​线性阶O(n)​</code>​,

线性对数阶​<code>​O(nlog2n)​</code>​,平方阶​<code>​O(n^2)​</code>​，立方阶​<code>​O(n^3)​</code>​,…，

k次方阶​<code>​O(n^k)​</code>​,指数阶​<code>​O(2^n)​</code>​。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

对于一个算法来说，空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

有时我们可以用空间来换取时间以达到目的。

长风破浪会有时，直挂云帆济沧海！