作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有这个算法:
function f(arr, i, n) {
if (i == n - 1) {
return arr[i];
}
if (i == 0) {
return (arr[i] + f(arr, i + 1, n)) / n;
} else {
return arr[i] + f(arr, i + 1, n);
}
}
这是一个递归算法,但它每圈只调用一次。
我认为它可能是一个带有 O(1 ^ n) 符号的算法,但如果是这样的话,
(1 ^ 1) = 1 (1 ^ 2) = 1 (1 ^ 3) = 1
等等
那不就是 O(1) 吗?用常量大 O 表示法?
最佳答案
在考虑时间复杂度之前,先问问自己:这个算法到底做了什么?这个问题可以帮助您建立评估分析的直觉。在这种情况下,我们取一组数字的平均值。
其次,什么是O(1)?这意味着无论数组有多大,算法都需要相同的时间来运行。因此,您的分析基本上是在争论,取一个包含 15 个元素的数组的平均值与一个包含 2000 万个元素的数组所花费的时间相同。所以这里有问题。
这是 O(n),因为算法访问每个元素一次,T(n) = T(n - 1) + 1
。每帧可能有 1 次递归调用,它使用 i + 1
进行下一次递归调用,像循环一样逐步遍历数组,并在每个调用帧完成持续工作。
顺便说一句,这是一个相当愚蠢的递归算法,因为每次调用问题空间并没有被分解太多。如果数组足够大并且函数调用会产生大量开销(至少在没有尾调用优化的语言实现中,这有效地将递归调用后没有计算的递归转换为循环),您可以轻松地炸毁堆栈。更不用说,代码并不比循环更容易理解。对于具有对数堆栈深度而非线性的问题,最好使用递归,除非问题非常小并且递归树很宽(例如指数),这占主导地位。
关于javascript - 递归遍历数组的大O算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66287125/
我是一名优秀的程序员,十分优秀!