整蛊时间复杂度 [英] Tricky time complexity

问题描述

我已经得到了pretty的善于揣摩的时间复杂度，但我仍然感到困惑如何确定指数时间的算法。下面的算法运行时间为O（K ^ n）的最坏情况。他们是如何得到这个值？第一个for循环需要的 N 的时间，第二个for循环需要的 K 的时间，第三个for循环使用的问：的是混乱的。如果运行时间的 N 的*的 K 的*的问：的-something，他们怎么O（K ^ N）？

  INT EXP（K，N）{
    功率= 1
    对于i = 1到n {
        NEWPOWER = 0
        对于j = 1至k {
            对于q = 1电源{
                NEWPOWER ++
            }
        }
        功率= NEWPOWER
    }
    返程（功率）
}
 

解决方案

0（K ^ N）似乎是正确的我。

在的J - 和 Q-环已累计 K *功率迭代。但动力呈指数每次更新 i循环迭代。

• 当 I = 1 ，的J - 和 Q-环的 K * 1 的迭代。
• 当 I = 2 ，的J - 和 Q-环的 K * K 迭代。
• 当 I = 3 ，的J - 和 Q-环的 K *（K * K）迭代。
• 当 I = M ，的J - 和 Q-环的 K *（K ^（M-1））迭代。

K *（K ^（M-1））只是 K ^ M ，其中1＆LT; = M＆LT; = N。因此，对于n次迭代，所有迭代的和渐进 0（K ^ N）。

I've gotten pretty good at figuring out time complexity, but am still confused about how to determine exponential time algorithms. The algorithm below has a worst case running time O(k^n). How did they get this value? The first for-loop takes n time, the second for-loop takes k time, and the third for-loop with q is confusing. If the running time is n * k * q-something, how did they get O(k^n)?

int exp(k, n) {
    power = 1
    for i = 1 to n {
        newpower = 0
        for j = 1 to k {
            for q = 1 to power {
                newpower++
            }  
        }
        power = newpower
    }
    return (power)
}

解决方案

O(k^n) seems correct to me.

The j-and q-loop has total k * power iterations. But power is updated exponentially each i-loop iteration.

• When i=1, j-and q-loop has k * 1 iterations.
• When i=2, j-and q-loop has k * k iterations.
• When i=3, j-and q-loop has k * (k*k) iterations.
• When i=m, j-and q-loop has k * (k^(m-1)) iterations.

k*(k^(m-1)) is just k^m, where 1 <= m <= n. So for n iterations, the sum of all iterations is asymptotically O(k^n).

这篇关于整蛊时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！