javascript - 如何通过重复加法计算一个数的幂的渐近运行时间？

Question

function calculatePower(k,n) {
var power = 1;
for(var i =0;i<n;i++) {
    var tempPower = 0;
    for(var j=0; j<k;j++) {
        for(var q=0; q<power; q++) {
            tempPower++;
        }
    }
    power = tempPower;
}
return power;
}
calculatePower(2,3);

我如何计算这样的运行时间？它会是 O(k+k^2+....+k^n) 还是 O(k^n) 的行？

Answer 1

由于 tempPower 将在 i 的每次迭代中初始化为 0，因此它将等于 k*power 对于每次迭代。因此，power = k*power 代码的时间复杂度为 T(k,n) = k + k^2 + k^3 + ... + k^n = k^{n+1} - 2 = Theta(k^{n+1})。