时空复杂度

字数

617 字

阅读时间

3 分钟

在计算时间复杂度和空间复杂度时，我们主要分析算法在最坏情况下的表现

[!summary]

• 时间复杂度：通过分析循环或递归执行的次数，确定算法操作的总执行次数，通常取决于输入规模。
• 空间复杂度：计算算法执行过程中使用的额外内存空间，通常关注输入数据之外的额外存储需求。

1 时间复杂度分析

我们看一下代码的主要结构：

public int removeElement(int[] nums, int val) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        if (nums[left] == val) {
            nums[left] = nums[right - 1];
            right--;
        } else {
            left++;
        }
    }
    return left;
}

1. 循环体：这个 while (left < right) 循环中的每一步操作都涉及到常数时间的操作：

   • nums[left] == val 是一个常数时间的检查操作。
   • nums[left] = nums[right - 1] 也是一个常数时间的替换操作。
   • right-- 是常数时间的操作。
   • left++ 也是常数时间的操作。

2. 迭代次数：

   • 在每次循环中，left 要么增加，要么 right 减少。每次迭代，left 或 right 其中之一会发生变化，意味着在最坏的情况下，我们最多进行 n 次迭代，其中 n 是数组的长度（nums.length）。

因此，整个 while 循环在最坏的情况下要执行 n 次。

• 时间复杂度：由于循环最多执行 n 次，且每次迭代中的操作都是常数时间操作，所以时间复杂度为 O(n)，其中 n 是数组的长度。

2 空间复杂度分析

1. 输入数组：这段代码并没有使用额外的数组空间，所有操作都是在原数组 nums 上进行的，因此没有额外的空间开销。

2. 局部变量：代码中使用了几个局部变量 left 和 right，这些都是常数大小的变量，不依赖于输入规模。

• 空间复杂度：由于我们只使用了常数数量的额外空间，空间复杂度为 O(1)。

3 总结

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)，因为没有使用额外的空间。