简单算法复杂度

Question

我有一个算法，我需要帮助找出它的复杂性（最严格的上限）

for(int i = 0; i < n/2; i++)
    for(int j = 0; j < n/4; j++)
        for(int k = 0; k < n; k++)
            x++;

我的分析是，如果每次for循环不分n的话，就是O(n^3)。这种复杂度仍然成立，因为每个 "for loop" 都会将每个操作减少到 O(log n) 复杂度，因为它会在每次循环执行时除以 n，使其越来越小（至少小于 O(n) ).

我会说答案在 O(log n) 和 O(n^3) 之间。你能帮我获得最严格的绑定吗？

Answer 1

for(int i = 0; i < n/2; i++)    --> n/2
    for(int j = 0; j < n/4; j++)  --> n/4
        for(int k = 0; k < n; k++)  --> n
            x++;

因此总复杂度为 O((n^3)/8) 即 O(n^3)

Answer 2

从内部循环开始：

for(int k = 0; k < n; k++)
    x++;

显然是 O(n)。

现在在上面一层：

for(int j = 0; j < n/4; j++)

是 O(n) 因为 j 需要 n/4 才能达到 n 我们知道 O( n/4) = O(n)

像这样的外循环是 O(n)。所以复杂度是 O(n^3) 因为你有三个嵌套循环，每个循环都是 O(n) 并且它们都不影响彼此。

Answer 3

假设每一步都需要时间 C。对于 k 循环，所用时间为 Cn。对于 j-loop，完成迭代所花费的时间是 (Cn)n/4=C(n^2)/4 对于 i-loop，完成迭代所花费的时间是 (C*(n^2)/4)n/2=C(n^3)/8

总耗时=(C/8)*(n^3)

由于 C/8 是一个常量，在考虑大 O 表示法时可以忽略它。因此，时间复杂度=O(n^3).

Simple Algorithm complexity