时空复杂度
字数
617 字
阅读时间
3 分钟
在计算时间复杂度和空间复杂度时,我们主要分析算法在最坏情况下的表现
[!summary]
- 时间复杂度:通过分析循环或递归执行的次数,确定算法操作的总执行次数,通常取决于输入规模。
- 空间复杂度:计算算法执行过程中使用的额外内存空间,通常关注输入数据之外的额外存储需求。
1 时间复杂度分析
我们看一下代码的主要结构:
java
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;
}
循环体:这个
while (left < right)
循环中的每一步操作都涉及到常数时间的操作:nums[left] == val
是一个常数时间的检查操作。nums[left] = nums[right - 1]
也是一个常数时间的替换操作。right--
是常数时间的操作。left++
也是常数时间的操作。
迭代次数:
- 在每次循环中,
left
要么增加,要么right
减少。每次迭代,left
或right
其中之一会发生变化,意味着在最坏的情况下,我们最多进行n
次迭代,其中n
是数组的长度(nums.length
)。
- 在每次循环中,
因此,整个 while
循环在最坏的情况下要执行 n
次。
- 时间复杂度:由于循环最多执行
n
次,且每次迭代中的操作都是常数时间操作,所以时间复杂度为 O(n),其中n
是数组的长度。
2 空间复杂度分析
输入数组:这段代码并没有使用额外的数组空间,所有操作都是在原数组
nums
上进行的,因此没有额外的空间开销。局部变量:代码中使用了几个局部变量
left
和right
,这些都是常数大小的变量,不依赖于输入规模。
- 空间复杂度:由于我们只使用了常数数量的额外空间,空间复杂度为 O(1)。
3 总结
- 时间复杂度:O(n),其中 n 是数组
nums
的长度。 - 空间复杂度:O(1),因为没有使用额外的空间。