同尺寸双输入数组函数的时间与空间复杂度咨询

1. 时间复杂度问题 #

题目明确两个数组尺寸相同，即n = m。第一个嵌套循环时间复杂度为O(n²)，第二个嵌套循环的O(m²)等价于O(n²)，两者相加后总时间复杂度为O(n² + n²) = O(n²)（大O表示法会忽略常数系数）。所以写成T(n,m)=O(n²)或者T(n,m)=O(m²)都是正确的，二者本质等价，通常会统一用其中一个变量来表示，比如O(n²)。

2. 空间复杂度问题 #

该函数的空间复杂度是O(1)。整个执行过程中仅使用了i、j这类固定数量的临时变量，没有开辟任何与输入数组规模挂钩的额外空间，所有操作都是直接在输入数组上进行的原地操作，属于常数级空间开销。

内容的提问来源于stack exchange，提问作者Rose