java - 简单算法复杂度

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++;

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

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

score 3 · Accepted Answer

从内循环开始：

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

score 3 · Accepted Answer

假设每一步花费时间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)。

score 2 · Accepted Answer

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)

3 回答 3