时间复杂度和空间复杂度

#AskCpp04 如何考量算法的效率？

时间复杂度

算法的时间复杂度（Time complexity）是一个定性描述该算法运行时间的函数，记作 T(n)。

但是，一个算法的运行时间必须得在计算机上运行测试才能确定，无法从理论上计算出来。实际中，我们只需要比较算法花费时间的差别即可，并不需要每个算法都上机测试。并且，算法花费的时间与算法中语句执行的次数成正比，这个执行次数称为语句频度或时间频度，也记为T(n)。

**通常表示为 T(n) = O(f(n)) **

举例

void func(int n) {
    for(int i = 0; i < n; i++) { // 需要执行 (n + 1) 次
        printf("Hello, World!\n"); // 需要执行 n 次
    }
}

上面的函数总共需要执行（n + 1 + n）= 2n + 1次，其时间复杂度为 O(n)。

计算时间复杂度有以下原则：

常见时间复杂度排序

*Ο(1)＜Ο(log*2n*)＜Ο(n)＜Ο(nlog*2n*)＜Ο(*n*2)＜Ο(*n*3)＜…＜Ο(*2*n)＜Ο(n!)*

常见时间复杂度列表

computational-complexity-of-algorithm

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

这里的存储空间主要包含两部分：