在学习算法基础知识的过程中,我对时间复杂度计算和运行代码时的实时消耗感到困惑。
演示代码说明了问题。
function calcDemo1(){
var init = 0;
for(var i=0;i<40;i++){
init += 0;
}
return init;
}
function calcDemo2(){
var init = 0;
init += (0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39);
return init;
}
- calcDemo1 的时间复杂度是否为 O(1),即使它是一个“for 循环”?
- 如果它们的时间复杂度都是 O(1),那么在运行代码时,它们在最坏情况下花费的时间是否相同?
相关问题是here
最佳答案
它们都具有常数时间复杂度。 O(1)
时间复杂度。
对于案例 1,有一个 for 循环,但它运行了 40 次。因此它将具有恒定的时间复杂度。
第二种情况,没有for循环,但还是常数时间加法。所以又是O(1)
。
这并不意味着如果有 for 循环,它的复杂度就不能保持不变。
作为对评论的回复,是的,即使我们增加硬编码值,时间复杂度也不会改变。它仍然是 O(1)
。
关于javascript - 一个关于时间复杂度计算和实时消耗的谜题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47281437/