如何计算给定Java函数的操作数？f(N)公式中除以2的来源是什么？

首先附上对应的Java代码：

public static String[] sum4(int N)
{
    //DO NOT COUNT IN opCount
    long opCount = 0;
    String fn = "f(N) = 5N+5(N(N-1)/2)+4";
    String On = "O(N) = n^2";
    //BEGIN opCounts
    long sum = 0;
    opCount++;// assignment of sum
    opCount++;//assignment of i
    opCount++;//comparison of I < N
    for(int i = 0; i < N; i++)
    {
        
        opCount++;//assignment of j
        opCount++;//comparison of j < i
        for(int j = 0; j < i; j++)//5N
        {
            sum++;
            opCount+=2;// sum addition and assignment
            opCount+=2;// J++ addition and assignment
            opCount++;// Comparison of J < I and the multiplier
        }
        opCount++;// I < N comparison
        opCount+=2;// I++
    }
    opCount++;//return
    return new String[] {fn, On, opCount+""};
}

公式中除以2的来源 #

你疑惑的N(N-1)/2来自内层循环的总执行次数，属于等差数列求和的计算结果：

• 外层循环的i取值范围为0,1,2,...,N-1，共执行N轮
• 每轮外层循环中，内层循环j的判断条件是j < i，也就是说当i=0时内层不执行，i=1时内层执行1次，i=2时执行2次，以此类推，i=N-1时内层执行N-1次
• 内层循环总执行次数为所有轮次执行次数的和：0+1+2+...+(N-1)，套用等差数列求和公式（首项+末项）*项数/2，可得总次数为N*(N-1)/2，这就是除以2的由来。

完整公式f(N) = 5N + 5*(N(N-1)/2) + 4的逐项推导 #

• 常量项+4：对应循环外的4次固定操作：
  • long sum = 0赋值1次
  • 外层循环变量i的初始赋值1次
  • 第一次i < N的比较操作1次
  • 最后的return操作1次
• 5N项：对应外层循环每轮的固定操作，共N轮，每轮操作数为5：
  • 内层循环变量j的初始赋值1次
  • 第一次j < i的比较操作1次
  • 本轮外层循环结束后i < N的比较操作1次
  • i++对应的加法和赋值操作2次
• 5(N(N-1)/2)项*：对应内层循环每次执行的固定操作，每执行1次内层循环对应5次操作，乘以总执行次数N(N-1)/2得到这部分总和：
  • sum++对应的加法和赋值操作2次
  • j++对应的加法和赋值操作2次
  • 下一轮j < i的比较操作1次

大O复杂度说明 #

公式中的最高次项为N²，当数据规模N趋向无穷大时，低次项和常量系数对整体复杂度的影响可以忽略，因此该算法的时间复杂度为O(n²)，和代码中标注的一致。 #

内容的提问来源于stack exchange，提问作者hyperspacewoo