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

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}).