迭代版本是线性的:
// O(n)
function factorial (n) {
let ret = 1;
for(let i = 2; i <= n; i++) {
ret = ret * i;
}
return ret;
}
对于递归版本,它似乎也是线性的:
function factorialR (n) {
if( n === 0 || n === 1 ) {
return 1;
} else {
return n * factorialR(n - 1);
}
}
递归版本也是线性的吗?而不是每个附加值的循环,它只是一个附加的函数调用。
最佳答案
你的两个函数都有 O(n)
在时间复杂度上。
第一个很简单。
第二个调用递归函数一次在每次迭代中,所以,它是 O(n)
以及。
关于javascript - 阶乘计算的大 O(时间复杂度)是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60079515/