一、时间复杂度

1. 什么是时间复杂度

时间复杂度用来描述：随着输入规模 N 增大，算法执行次数的增长趋势。

2. 大 O 表示法

假设某段代码的基本操作次数是：

F(N) = N² + 2N + 10

大 O 分析时，只看增长趋势，因此遵循三个规则。

(1) 去掉常数项

N² + 2N + 10

其中 10 是常数项，随着 N 增大影响很小，可以忽略：

N² + 2N

(2) 只保留最高阶项

当 N 很大时，N² 的增长速度远大于 2N，所以保留：

N²

(3) 去掉最高阶项的系数

如果是：

2N²

仍然记作：

O(N²)

所以：

F(N) = N² + 2N + 10

最终时间复杂度是：

O(N²)

3.常见代码片段分析

(1) 双层循环：O(N²)

void func1(int N) {
    int count = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            count++;
        }
    }

    for (int k = 0; k < 2 * N; k++) {
        count++;
    }

    int M = 10;
    while ((M--) > 0) {
        count++;
    }

    System.out.println(count);
}

执行次数：

N² + 2N + 10

其中：

• 双层循环执行 N * N = N² 次
• 单层循环执行 2N 次
• while 循环执行 10 次

根据大 O 规则，只保留最高阶项：

O(N²)

(2) 单层循环：O(N)：

void func2(int N) {
    int count = 0;

    for (int k = 0; k < 2 * N; k++) {
        count++;
    }

    int M = 10;
    while ((M--) > 0) {
        count++;
    }

    System.out.println(count);
}

执行次数：

2N + 10

去掉常数项和系数后：

O(N)

(3) 两个独立变量：O(N + M)：

void func3(int N, int M) {
    int count = 0;

    for (int k = 0; k < M; k++) {
        count++;
    }

    for (int k = 0; k < N; k++) {
        count++;
    }

    System.out.println(count);
}

第一个循环执行 M 次，第二个循环执行 N 次。

总执行次数：

N + M

所以时间复杂度是：

O(N + M)

注意：如果 N 和 M 没有明确关系，不能随便简化成 O(N) 或 O(M)。

(4) 固定次数循环：O(1)

void func4(int N) {
    int count = 0;

    for (int k = 0; k < 100; k++) {
        count++;
    }

    System.out.println(count);
}

循环固定执行 100 次，不会随着 N 增大而变化。

所以时间复杂度是：

O(1)

O(1) 不是只执行 1 次，而是表示执行次数是常数级别。

4.常见算法时间复杂度

(1) 冒泡排序：O(N²)

void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;

        for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
                swap(array, i - 1, i);
                sorted = false;
            }
        }

        if (sorted == true) {
            break;
        }
    }
}

冒泡排序的核心是相邻元素比较。

最坏情况下，比较次数大约是：

(N - 1) + (N - 2) + (N - 3) + … + 1

这是等差数列求和

N(N - 1) / 2

展开后：

1/2N² - 1/2N

去掉低阶项和常数系数：

O(N²)

这段代码带有 sorted 优化，因此不同情况复杂度如下：

情况	时间复杂度
最好情况：数组本身有序	O(N)
最坏情况：数组逆序	O(N²)
平均情况	O(N²)

(2) 二分查找：O(logN)

int binarySearch(int[] array, int value) {
    int begin = 0;
    int end = array.length - 1;

    while (begin <= end) {
        int mid = begin + ((end - begin) / 2);

        if (array[mid] < value) {
            begin = mid + 1;
        } else if (array[mid] > value) {
            end = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

二分查找每次都会把查找范围缩小一半：

N
N / 2
N / 4
N / 8
…
1

假设执行了 x 次后，规模缩小到 1：

N / 2^x = 1

得到：

2^x = N

所以：

x = log₂N

因此二分查找的时间复杂度是：

O(logN)

在大 O 表示法中，log 的底数通常不重要，因为不同底数之间只差一个常数倍。

(3) 阶乘递归：O(N)

// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
}

递归调用过程：

factorial(N)
factorial(N - 1)
factorial(N - 2)
…
factorial(1)

每次递归都让 N 减少 1，所以递归调用次数约为 N 次。

时间复杂度：

O(N)

(4) 斐波那契递归：O(2ᴺ)

int fibonacci(int N) {
    return N < 2 ? N : fibonacci(N - 1) + fibonacci(N - 2);
}

每次调用 fibonacci(N)，都会继续调用：

fibonacci(N - 1)
fibonacci(N - 2)

递归会展开成一棵树，存在大量重复计算。

节点数量近似为：

2^0 + 2^1 + 2^2 + … + 2^(N - 1)

等比数列求和后约为：

2^N - 1

所以普通递归版斐波那契的时间复杂度通常记为：

O(2^N)

二、空间复杂度

空间复杂度用于衡量：

算法在运行过程中，额外使用的存储空间 随输入规模增长的变化趋势。

常数额外空间：O(1)：

示例：冒泡排序

void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
        for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
        if (sorted == true) {
            break;
        }
    }
}

这段代码中，额外使用的变量主要有：

end、sorted、i

这些变量的数量是固定的，不会随着数组长度 N 的增大而增加。

所以冒泡排序的空间复杂度是：

O(1)

线性额外空间：O(N)：

示例：用数组保存斐波那契数列

int[] fibonacci(int n) {
    int[] fibArray = new int[n + 1];

    fibArray[0] = 0;
    fibArray[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }

    return fibArray;
}

这段代码内部新建了一个数组：

int[ ] fibArray = new int[n + 1];

数组长度是 n + 1，会随着输入规模 n 的增大而增大。

因此额外空间规模为：

n + 1

根据大 O 表示法，忽略常数项后：

O(N)

所以该算法的空间复杂度是：

O(N)

注意

如果只需要返回第 n 个斐波那契数，而不是返回整个数组，可以只用两个变量保存前两项：

int fibonacci(int n) {
    if (n < 2) {
        return n;
    }

    int prev = 0;
    int curr = 1;

    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }

    return curr;
}

这时只使用固定数量的变量，空间复杂度可以优化为：

O(1)

递归空间复杂度：看调用栈深度

递归算法的空间复杂度不能只看代码里有没有创建数组，还要看 递归调用栈。

递归阶乘：O(N)

示例

long factorial(int N) {
    return N < 2 ? N : factorial(N - 1) * N;
}

调用过程大致如下：

factorial(N)
factorial(N - 1)
factorial(N - 2)
…
factorial(1)

递归每次让 N 减少 1，直到到达终止条件。

所以最大递归深度约为：

N

每一层递归只使用常数级空间，因此总栈空间为：

N * O(1)

所以空间复杂度是：

O(N)

三、练习题

1.消失的数字

解法一: 求和法

public int missingNumber(int[] nums) {
    int n = nums.length;
    // 1. 计算 0 到 n 的理想总和
    int expectedSum = n * (n + 1) / 2;
    
    // 2. 计算数组中现有数字的实际总和
    int actualSum = 0;
    for (int num : nums) {
        actualSum += num;
    }
    
    // 3. 差值即为缺失值
    return expectedSum - actualSum;
}

时间复杂度

代码只遍历了一次数组：

所以时间复杂度是：

O(n)

空间复杂度

只使用了几个变量：

n、expectSum、actualSum

所以空间复杂度是：

O(1)

解法二: 异或法

如果把 0 ~ n 和数组中的所有数字全部异或，出现两次的数字会相互抵消，最后剩下的就是缺失的数字。

class Solution {
    public int missingNumber(int[] nums) {
        int x = 0;

        for (int i = 0; i <= nums.length; i++) {
            x ^= i;
        }

        for (int num : nums) {
            x ^= num;
        }

        return x;
    }
}

复杂度同样是：

时间复杂度：O(n)
空间复杂度：O(1)

2.轮转数组

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 步骤1：防止 k 大于数组长度

        // 步骤2：翻转整个数组
        reverse(nums, 0, n - 1);
        // 步骤3：翻转前 k 个元素
        reverse(nums, 0, k - 1);
        // 步骤4：翻转后面剩余的元素
        reverse(nums, k, n - 1);
    }

    // 辅助函数：翻转数组中从 start 到 end 的部分
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

时间复杂度

三次翻转，每个元素最多被交换常数次。

O(n)

空间复杂度

只使用了几个变量：

n、k、start、end、temp

所以空间复杂度是：

O(1)