该程序段的基本语句是 for 循环语句。
执行次数计算公式如下:
(1) for(i=1;i <=n;i++)
执行次数:n 次(因为 i 的值从 1 到 n 执行了 n 次循环)。
(2) for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
执行次数:n^2 次。两个 for 循环,分别执行了 n 次,总共执行了 n*n=n^2 次。
(3) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
执行次数:(n^2+n)/2 次。外层 for 循环执行了 n 次,内层 for 循环执行了 1 + 2 + 3 + ... + n = n(n+1)/2 次。因此总的执行次数为 n(n+1)/2,即 (n^2+n)/2。
总结:
在复杂度分析过程中,我们可以通过分析程序段的基本语句执行次数来确定其时间复杂度。对于 for 循环来说,通常只需要确定循环执行次数即可,具体计算公式会根据循环体的复杂度而有所不同。