算法复杂度

• 定义：算法在执行过程中，所消耗的时间和空间（内存）资源。

算法复杂度，包括时间复杂度和空间复杂度。

时间复杂度

指执行算法所需要的计算工作量。
即所有语句频度（语句执行次数）之和。

int TestSum(int n) {
    int sum = 0;
    // 各语句的频度
    for (int i = 0; i < n; i ++) { //n+1
        sum ++; //n
        for (int j = 0; j < n; j ++) { //n*(n+1)
            sum ++; //n²
            for (int k = 0; k < n; k ++) { //n²*(n+1)
                sum ++; //n³
            }
        }
    }
}

• 以上算法的时间频度之和为：$T(n)=2n^3+3n^2+3n+1$
• 当n趋向无穷大时，显然有$T(n) \approx O(n^3)$，其中，O(Big-O notation)称为渐进符号。
• 记作$T(n)=O(n^3)$是算法TestSum的渐近时间复杂度

空间复杂度

指算法在计算机内执行时所需存储空间的度量。
即执行该算法所需要占用的内存空间。

算法执行期间所需要的存储空间包括：

• 算法程序所占的空间；
• 输入的初始数据所占的存储空间；
• 算法执行过程中所需要的额外空间。