代码的三个求和：计算原始操作的数量和大 O 符号

Question

我有以下代码：我需要获取大O符号并计算原始操作的数量。我知道循环通常对应于数学求和。有人可以帮助阐明如何解决以下代码的大 O，知道求和吗？

public static int hello(int[] first, int[] second) { // assume equal-length arrays
    int n = first.length, count = 0;
    for (int i = 0; i < n; i++) { // loop from 0 to n-1           
        int total = 0;
        for (int j = 0; j < i; j++) {// loop from 0 to i
            for (int k = 0; k <= j; k++) { // loop from 0 to j
                total += first[k];
            }
        }
        if (second[i] == total) {
            count++;
        }
    }
    return count;
}

所以这将是正确的？你如何从这里继续？

当运行n=10的代码时，第一个循环运行n次即10次，第二个循环级别的语句运行45次，不知道是什么意思n 和在内部第三个循环级别具有恒定时间的语句运行 165 次。

有人可以帮助我了解此代码的求和类型以及它如何转换为 Big O 吗？非常感谢您的帮助。

Answer 1

前n个自然数之和和前n个自然数的平方和为，

你的求和是正确的，所以解决它

S_n =

S_n≤

S_n≤

S_n≤

S_n 转换为 for 循环总共执行的操作数。
时间复杂度因此给出， O(S_n) ~ O(n³)

代码的三个求和：计算原始操作的数量和大 O 符号

Three summations intertwined of a code: counting number of primitive operations & big O notation

algorithm

big-o