2

我有一个算法,我需要帮助找到它的复杂性(最严格的上限)

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

我的分析是,如果 n 不会在每个 for 循环中被划分,它将是O(n^3). 这种复杂性仍然成立,因为每个“for 循环”都会将每个操作降低到一个O(log n)复杂性,因为它在每次循环执行时都将 n 相除,使其越来越小(O(n)至少小于)。

我会说答案在O(log n)和之间O(n^3)。你能帮我找到最紧的界限吗?

4

3 回答 3

3

从内循环开始:

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),并且它们之间没有相互影响。

于 2015-05-12T11:36:20.320 回答
3

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

所以总时间=(C/8)*(n^3)

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

于 2015-05-12T12:32:07.713 回答
2
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)

于 2015-05-12T11:33:12.563 回答