求给定代码在渐近分析中对应的二次方程表达式

目标代码如下：

int func(int n)
{
   int sum = 0;
   for(int i = 1; i <= n; i++)
      for(int j = 1; j <= i; j++)
          sum++;
   
   return sum;
}

逐行分析核心操作执行次数 #

• 初始化语句int sum = 0;仅执行1次，属于常数级操作，不影响二次项结构。
• 外层循环for(int i = 1; i <= n; i++)会执行n次完整迭代，每次迭代对应一个i值（从1到n）。
• 内层循环for(int j = 1; j <= i; j++)的执行次数由当前i决定：当i=1时执行1次，i=2时执行2次，……，i=n时执行n次。
• sum++是核心操作，每次内层循环执行1次，因此总执行次数为所有内层循环次数的总和：$1+2+3+...+n$。

推导二次方程 #

上述求和式是首项为1、末项为n的等差数列求和，代入等差数列求和公式：
$$\sum_{k=1}^n k = \frac{n(n+1)}{2}$$

将公式展开后，得到核心操作执行次数对应的二次方程：
$$\frac{1}{2}n^2 + \frac{1}{2}n$$

（可选）所有语句总执行次数的二次方程 #

如果统计所有语句的执行次数（包括循环初始化、条件判断、递增操作等），总和计算如下：

1. 初始化与返回操作：sum=0和return sum共执行2次
2. 外层循环：初始化i=1执行1次，条件判断i<=n执行n+1次，i++执行n次，合计2n+2次
3. 内层循环：初始化j=1执行n次，条件判断j<=i总次数为$\frac{n(n+1)}{2}+n$，j++总次数为$\frac{n(n+1)}{2}$，合计$\frac{n^2+3n}{2} + \frac{n^2+n}{2} + n = n^2+3n$次
4. 核心操作sum++：$\frac{n(n+1)}{2}$次

将所有次数相加并整理，得到总执行次数的二次方程：
$$\frac{3}{2}n^2 + \frac{11}{2}n + 5$$

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