从时间复杂度生成多项式函数

Question

我正在为几天后的考试做考试复习，我遇到了这个问题。 “计算以下代码中的分配次数（包括所有循环计数器初始化和增量）。现在在考试页面上以纯文本形式记录您的工作。将您的答案作为 n 的多项式函数给出（不要使用 O、Theta、或 Omega 表示法）。

for(i = 0; i < n; ++i){

    for(j = 0; j<i+1; ++j){

               sum +=a[j];

   }
}

据我所知，这是 O(n^2)，因为它是嵌套循环（我知道这是错误的，因为问题表明不要使用 O 符号）。我遇到的关于这个主题的所有示例都简化为 O 表示法。

答案是否和

一样简单

n^2 + n?

因为sum +=a[j]执行了n次，for(j = 0; j<i+1; ++j{也执行了n*n次

Answer 1

i   j   sum     notes
0   0   +=a[0]
0   1   -       break the inner loop
1   0   +=a[0]
1   1   +=a[1]
1   2   -       break the inner loop
2   0   +=a[0]
2   1   +=a[1]
2   2   +=a[2]
2   3   -       break the inner loop
... ...
n-1 n-1 +=a[n-1]
n-1 n   -       break the inner loop
n   -   -       break the outer loop

您对变量 i 进行了 n 次赋值（从 0 到 n-1）加上最后一次赋值（打破外循环的那一次），总共 n+1.
对于每个外循环，您有 i+1 个变量赋值 j 加上最后一个（打破内循环的那个），总共 2+3+4+...+(n+1) = (n+1)(n+2)/2-1。
对于每个外循环，您有 i+1 个变量 sum 的赋值，总共 1+2+3+...+n = n(n+1)/2.

作业总数为n+1 + (n+1)(n+2)/2-1 + n(n+1)/2，即n^2 + 3n + 1。

从时间复杂度生成多项式函数

Generating a polynomial function from time complexity

algorithm

time-complexity