嵌套依赖for循环的理论时间复杂度计算

Question

如何计算以下具有相关索引的嵌套 for 循环的大 O 时间复杂度：

void function1 (int n)
{
     int x = 0;
     for (int i = 0; i <= n/2; i+=3)
        for (int j = i; j <= n/4; j+=2)
           x++;
}

Answer 1

代码的复杂性定义为您的代码将针对给定的 n 执行多少次。
有两种方法可以做到这一点。

模拟：运行不同值的代码n并找出值。在这种情况下，这相当于 x.
理论值：

让我们首先检查每个 i 您的代码运行了多少次：
用等差数列公式(a_n = a_1 + (k-1)*d):

i=0 => n/4 = 0 + (k-1)*2 => n/8 + 1 次
i=3 => n/4 = 3 + (k-1)*2 => (n-12)/8 + 1 次
i=6 => n/4 = 6 + (k-1)*2 => (n-24)/8 + 1 次
i=9 => n/4 = 9 + (k-1)*2 => (n-36)/8 + 1 次

我们现在检查最后一个i's：
i=n/4 => n/4 = n/4 + (k-1)*2 => 1 次
i=n/4 - 3 => n/4 = (n/4-3) + (k-1)*2 => 3/2 + 1 次
i=n/4 - 6 => n/4 = (n/4-6) + (k-1)*2 => 6/2 + 1 次

所以内循环的总次数运行是：

= (1) + (3/2 + 1) + (6/2 + 1) + (9/2 + 1) ...  + ((n-12)/8 + 1)+ (n/8 + 1)
=> (0/2 + 1) + (3/2 + 1) + (6/2 + 1) + (9/2 + 1) ...  + ((n-12)/8 + 1)+ (n/8 + 1)

可以写成：

=> (0/2 + 3/2 + 6/2 + ... (n-12)/8 + n/8) + (1 + 1 + 1 ... 1 + 1)

让我们假设系列中共有 P 项：
让我们找出P：

n/8 = (0/2) + (P-1)*(3/2)   =>   P = (n+12)/12

现在总结以上系列：

= [(P/2) (0/2 + (P-1) * 3/2)] + [P]
= P(3P+1)/4
= (n+12)(3(n+12)+12)/(4*12*12)
= (n^2 + 28n + 96)/192

所以代码的最终复杂度是

= (number of operation in each iteration) * (n^2 + 28n + 96)/192

现在看看术语 (n^2 + 28n + 96)/192 对于非常大的 n 这将接近 ~n^2

复杂度对比如下：
线性比例很难分析到我绘制的对数比例。虽然对于小 n 你看不到复杂性收敛到 n^2.

Answer 2

使用一种非常放松的方法，可以这样说：

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

与 :

相同

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

因为 i > n/4 内部循环将不会执行。此外，为了简化数学运算，您可以说代码与以下内容大致相同：

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

因为上下文是big-O，所以对于双循环上限的计算没有影响。形式循环的迭代次数：

    for (int j = a; j < b; j += c)

可以用公式(b - a) /c计算。因此，内部循环将运行大约 ((n/4) - i) / 2) 次，或 n/8 - i/2 次。

外循环可以被认为是从 k=0 到 n/12 的运行ning。所以对于两个循环我们有

the summation of [k=0 to n/12] of (n/8 - 3k/2),

相当于

the summation [k=0 to n/12] of n/8  -  the summation [k=0 to n/12] of 3k/2.

因此，

(N^2) / 96 - the summation [[k=0 to n/12] of 3k/2

大约是 (n^2) / 192。因此，上限为O (n^2).

嵌套依赖for循环的理论时间复杂度计算

Theoretical time complexity calculation of nested dependent for loops

language-agnostic

complexity-theory

big-o

time-complexity

nested-loops