java - 计算 BigOh，迭代除法

Question

有一个硬件分配来计算 BigOh，但我循环中的迭代给我带来了问题。

循环：

public static int fragment4b(int n){
    int sum = 0;
    for(int i = 1; i <= n*n; i++)         
        for(int j = i; j>= 1; j /=2)        
            sum +=j; 
}

我理解外部循环有 O(n*n)，但我觉得我的内部有问题

所以我知道内部循环有 O( (ln(i)/ln(2)) + 1 ) 这看起来对吗？或者我叫错了树

Answer 1

内部循环sum+= j完全重复该语句

并且外部循环重复此 N^2 次。

所以操作的总数是从 1 到 N^2 的内循环的总和，如下所示：

那就是

编辑：记录日志时，请发言。

Answer 2

我将计算运行时间如下：

T = log1 + log2 + log3 + ... + log(n^2)

在上面的公式中，第一项是外循环第一次迭代的运行时间，第二项是第二次迭代的运行时间，以此类推。

很明显：

T < log(n^2) + log(n^2) + ... + log(n^2) = 2(n^2)logn = O(n^2logn))

所以运行时间是有界的O(n^2logn)。