3个嵌套for循环的大O？

Question

public int Loop(int[] array1) {
        int result = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1.length; j++) {
                for (int k = 1; k < array1.length; k = k * 2) {
                    result += j * j * array1[k] + array1[i] + array1[j];
                }
            }
        }
        return result;
    }

我试图找到复杂度函数来计算这里的算术运算次数.我知道复杂性类是O(n ^ 3),但是我在计算步骤时遇到了一些麻烦.

到目前为止,我的理由是我计算算术运算的数量是8,那么复杂度函数是8n ^ 3吗？

非常感谢任何正确方向的指导,谢谢!

Answer 1

第一个循环将运行n时间,第二个循环将运行n时间,但第三个循环将运行log(n)时间(基数2).因为k每次逆操作都要乘以2 来乘以日志.乘以我们的O(n^2 log(n))