具有不同内部循环的嵌套循环的复杂性

非常类似的复杂性示例。我想了解这些问题如何变化。考试即将明天:(任何快捷方式在这里找到的复杂具有不同内部循环的嵌套循环的复杂性

CASE 1：

void doit(int N) { 
    while (N) { 
     for (int j = 0; j < N; j += 1) {} 
    N = N/2; 
    } 
}

案例2：

void doit(int N) { 
    while (N) { 
     for (int j = 0; j < N; j *= 4) {} 
    N = N/2; 
    } 
}

案例3：

void doit(int N) { 
    while (N) { 
     for (int j = 0; j < N; j *= 2) {} 
    N = N/2; 
    } 
}

谢谢这么多！

来源

2012-12-12 bluejamesbond

的答案，一个号码是O（N）...但我不知道如何解决数学吧，就是有人可以点我怎么做的答案吧会很好。如果你看一下这里的第一个答案，艾米特已经证明了它在数学上，类似的东西将是巨大的：http://stackoverflow.com/questions/13818794/complexity-for-a-nested-loop-with-growing-internal-loop – bluejamesbond

void doit(int N) { 
    while (N) { 
    for (int j = 0; j < N; j += 1) {} 
    N = N/2; 
    } 
}

要找到这个O（），请注意，我们将N除以2每次迭代。所以，（不要侮辱你的智慧，但为了完整性）通过循环的最终非零迭代，我们将有N = 1。之前的时间我们将有N = a（2），然后在那之前N = a（4）...其中0 < a < N（注意那些是非包含边界）。所以，这个循环将执行总共log（N）次，这意味着我们看到的第一次迭代N = a2 ^（floor（log（N）））。

为什么我们关心这件事？嗯，这是它有一个很好的封闭形式几何级数：

Sum = \sum_{k=0}^{\log(N)} a2^k = a*\frac{1-2^{\log N +1}}{1-2} = 2aN-a = O(N).

如果有人能想出如何获取latexy符号正确地对我，我真的很感激它显示。

来源

2012-12-12 06:08:55 NickO

您已经有了答案number 1 - O(n)，由@NickO给出，这里是一个替代解释。

表示由T（N）内循环的外重复的数目，而让外循环的数目是h。需要注意的是h = log_2(N)

T(N) = N + N/2 + ... + N/(2^i) + ... + 2 + 1 
    < 2N (sum of geometric series) 
    in O(N)

编号3：是O((logN)^2)

由T（n）表示内环的外重复的数目，而让外循环的数目是h。需要注意的是h = log_2(N)

T(N) = log(N) + log(N/2) + log(N/4) + ... + log(1) (because log(a*b) = log(a) + log(b) 
    = log(N * (N/2) * (N/4) * ... * 1) 
    = log(N^h * (1 * 1/2 * 1/4 * .... * 1/N)) 
    = log(N^h) + log(1 * 1/2 * 1/4 * .... * 1/N) (because log(a*b) = log(a) + log(b)) 
    < log(N^h) + log(1) 
    = log(N^h)          (log(1) = 0) 
    = h * log(N)         (log(a^b) = b*log(a)) 
    = (log(N))^2         (because h=log_2(N))

数2几乎是相同的编号3.

（在2,3：1假设j开始，而不是从0，如果这不是这种情况@WhozCraig给予为什么它从来没有断的原因）

来源

2012-12-12 06:41:37 amit

具有不同内部循环的嵌套循环的复杂性

回答

相关问题