时空复杂度

时空复杂度，即算法的时间复杂度和空间复杂度。算法复杂度是评价一种算法优劣的重要标准，可以通过它来初步判断一段代码能否被题目所接受，得到正确答案（AC）。其中，时间复杂度通常更重要，须加分析，因为传统题目的空间限制通常是足够的（如 128.00MB 或 256.00MB），而时间限制却很紧迫（常见的有 1.00s ，有一些题目因为要求困难，时间限制可能是 2.00s 甚至更宽松。但这类题目通常也需要低复杂度的算法）。

时间复杂度

首先来看一段代码：

/* 样例1 */
int sum = 0;
for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        for (int k = 1; k <= n; ++ k)
            sum += i + j + k;

程序中出现了三层循环。其中，第一层循环从 1 到 n 共循环了 n 次，第二层和第三次也是如此。故：时间频度 T(n) = n³ （注意：是时间频度，不是时间复杂度，这两者的区别极大），时间复杂度 O(n³) 。为什么呢？因为一层循环 n 次，三层循环就有 n×n×n 即 n³ 次。

第二段代码：

/* 样例2 */
int sum = 0;
for (int i = 1; i <= n - 1; ++ i)
    for (int j = 1; j <= n - 1; ++ j)
        for (int k = 1; k <= n - 1; ++ k)
            sum += i + j + k;

和样例1差不多，三层循环，不过循环次数从 n 降到了 n - 1 。故：时间频度 T(n) = (n - 1)³ ，时间复杂度 O(n³) 。为什么呢？不是循环 (n - 1)³ 次吗？

时间复杂度忽略常数，除了次幂。

第三段代码：

/* 样例3 */
int sum = 0;
for (int i = 1; i <= n; ++ i)
    sum += i;
for (int j = 1; j <= n; ++ j)
    for (int k = 1; k <= n; ++ k)
        sum += j + k;