这个函数的时间复杂度是O(n)还是O(log(n))。
function reverse(array) {
for (var i = 0, j = array.length - 1; i < j; i++, j--) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
乍一看,它似乎对输入进行了 n/2 次迭代。然而,如果你仔细想想,实际的低级操作数量接近于 2n。
最佳答案
所以假设你有一个长度为 n
的字符串
然后你有指标i=0
,和j = n-1
循环一直持续到 i>=j
,其中 j
减 1,i
加 1
这将为您提供总共 n/2
次迭代。
在循环内,您总共有 3 个语句,这意味着该循环将总共完成 3(n/2)
。除此之外,您在循环外还有 1 个操作,留给我们
f(n) = 3(n/2)+1 which is O(n)
编辑:这假设循环维护操作(i++
,j--
)是微不足道的,这是处理 Big Oh 符号时的常见做法
关于javascript - 这个就地数组反转的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41047128/