如何使用大 O 表示法计算两个嵌套循环的运行时间？

Question

所以我想计算出以下算法的运行时间（伪代码）：

Algorithm(N):
    int i = n;
    int j;
    new Array sum[(n + 1) / 2];
    while i > 1 do
        j = i;
        while j < n do
            for k = 0; k < n; k = k + 2 do
                sum[k / 2] = sum[(k / 2) - 1] + k;
            end
            j = j * 2;
        end
        i = i / 2;
    end 
    return sum

Answer 1

外循环将使_⌊log_₂_⌋ 次迭代。

中间循环会在第一次运行时进行0次迭代，然后是1次，然后是2次，然后是3次，...直到_⌊log_₂_⌋。这是一个 triangular number，因此中间循环的总执行次数等于：

_⌊log_₂_⌋( _⌊log_₂_⌋ + 1) / 2

内部循环对于中间循环的每次迭代总是进行相同的迭代次数，因为它与 or 的值无关：它是 / 2。所以总共会有以下迭代次数:

_⌊log_₂_⌋( _⌊log_₂_⌋ + 1) / 4

算术计算的时间复杂度有两种计算方式：

在第一种方法中，我们假设所有涉及的算术计算都是在恒定时间内执行的（如加法、减法、除以 2 和乘以 2），因此我们可以推导出以下渐近线顺序：

O(_⌊log_₂_⌋(_⌊log_₂_⌋ + 1) / 4) = O(log²)
更纯粹的方法不假设算术计算是在恒定时间内执行的，考虑到整数不存储在有限的字中（如 64 位），而是可以任意长。这意味着上述算术计算具有 O(log) 时间复杂度。所以我们必须添加那个因素，因为这些被用在内部循环的主体中：

O(log³)

作业应指定使用两种方法中的哪一种。

如何使用大 O 表示法计算两个嵌套循环的运行时间？

How do I calculate the runtime of two nested loops with the big-O Notation?

algorithm

runtime

big-o