以下循环的复杂性分析

Question

我有一些双循环复杂度分析的练习题，不知道自己做的对不对。

for i = 1 to n do 
    j = i
    while j < n do 
        j = 2∗j 
    end while 
end for

我对此的回答是 O(n^2)，因为第一个循环是运行 O(n) 次，而内部循环正在对 [=54= 进行 O(n/2) 次迭代] 外循环的迭代。所以 O(n) * O(n/2) = O(n^2).

再进一步看，我想我可以说内部循环正在做部分求和，即 O(n/2) + O(n-1) + ... + O(1)，这也是 O(n)

        for i = 1 to n do 
            j = n 
            while i∗i < j do 
                j = j − 1 
            end while 
        end for

同样，外循环是 O(n)，而内循环在最差的迭代中执行 O(sqrt(n))，所以我认为这是 O(n*sqrt(n))，但我不确定这个.

       for i = 1 to n do 
            j = 2 
            while j < i do 
                j = j ∗j 
            end while 
        end for

这里的外循环是 O(n)，而内循环正在为最坏的情况做 O(logn) 工作。因此我认为这是 O(nlogn)

        i = 2 
        while (i∗i < n) and (n mod i != 0) do 
            i = i + 1 
        end while

最后，我不知道如何理解这个。因为模运算符。

我的问题是：

我在前 3 个示例中做错了什么吗？
我正在做的内部循环的“最坏情况方法”是否正确？
我应该如何完成最后一个练习？

Answer 1

对于内循环中的第一个，我们有： i, 2*i, 4*i, ... , (2^k)*i 其中 (2^k)*i < n。所以k < logn - logi。您所说的外循环重复 n+1 次。我们总共有这个总和：

$one$

等于

$sec$

因此我认为复杂度应该是O(nlogn).

第二个我们有：

$thi$

第三个：

$fo$

所以我觉得应该是O(log(n!))

最后一个，如果n是偶数，那么就是O(1)，因为我们不进入循环。但最坏的情况是 n 是奇数，不能被任何平方数整除，那么我认为应该是

$fif$

Answer 2

第一个问题：
内部循环需要 log(n/i) 时间。上限为 O(log(n))，总时间为 O(n*log(n))。下限是 log(n/2) 并且仅对最后的 n/2 项求和，给出总复杂度 n/2 * log(n/2) = n/2*log(n) - n/2 = O(n * log(n)) 并且我们得到 O(n* log(n)) 的界限很紧（我们有一个 theta边界）。

第二个问题：
内部循环需要 n - i^2 时间（如果 i^2 >= n 则需要 O(1)）。请注意，对于 i >= sqrt(n)，内部循环需要 O(1) 时间，因此我们可以运行仅针对 i in 1:sqrt(n) 的外部循环，并将 O(n) 添加到结果中。内循环的上限为 n，总时间为 O(n * sqrt(n) + n) = O(n ^ (3/2))。内循环的下限是 3/4 * n 并且仅对 i 求和到 sqrt(n) / 2 （因此 i^2 < n / 4 和 n - i ^ 2 > 3/4 * n ）我们得到Ω(sqrt(n) / 2 * n * 3/4 + n) = Ω(n^(3/2)) 的总时间因此边界 O(n * sqrt(n)) 确实很紧。

第三题：
在这个 j 中，我们从 2 开始计算它的平方，直到它达到 i。在内部循环的 t 步之后，j 等于 2^(2^t)。我们在 j = 2 ^ (log(i)) = 2 ^ (2 ^ log(log(i))) 时达到 i，即在 t = log(log(i)) 步之后。我们可以再次像前面的问题一样给出上界和下界，并得到紧界 O(n * log(log(n)))。

第四题：
复杂度可以在 2 = O(1) 和 sqrt(n) 之间变化，具体取决于 n 的因式分解。在最坏的情况下，n 是一个完美的正方形，复杂度为 O(sqrt(n)

最后回答你的问题：
1. 是的，你做错了一些事情。您在 1 和 3 中得出了错误的答案，在 2 中您的结果是正确的，但推理有缺陷；正如您在我的分析中已经看到的那样，内部循环不是 O(sqrt(n))。
2. 考虑到内循环的 "worst case" 很好，因为它给了你一个上限（这在这类问题中大多是准确的），但要建立一个紧密的界限，你还必须显示一个下限，通常就像我在一些例子中所做的那样，只采用较高的术语并将它们降低到第一个。证明紧界的另一种方法是使用已知级数的公式，例如 1 + ... + n = n * (n + 1) / 2，给出 O(n^2) 的直接界，而不是 1 + ... + n >= n/2 + ... + n >= n/2 + ... + n/2 = n/2 * n/2 = n^/4 = Ω(n^2) 的下界。
3. 上面已经回答了。

以下循环的复杂性分析

Complexity Analysis of the following loops

complexity-theory