C#代码片段的Big O时间复杂度计算求助

关键前提 #

LinkedList<T>.ElementAt(int index) 的时间复杂度为 O(index)：因为LinkedList是双向链表，没有随机访问能力，调用ElementAt时需要从链表头部（或尾部，取决于索引位置）逐个遍历到目标索引节点，最坏情况下需要遍历index个节点。

逐行时间复杂度梳理 #

初始化阶段 #

int n = Int32.Parse(Console.ReadLine());                 // O(1)：固定输入解析操作
LinkedList<int> sumSequence = new LinkedList <int>();    // O(1)：链表实例化开销固定
sumSequence.AddLast(0);                                  // O(1)：LinkedList.AddLast为常数时间操作
sumSequence.AddLast(1);                                  // O(1)：同上

第一个外层循环（核心计算逻辑） #

for (int i = 2; i < n; i++)                              // 执行次数：n-2 次，时间复杂度O(n)（仅循环本身）
{
  int currentSum = 0;                                    // O(1)：每次迭代的常数赋值操作

  // 内层循环：j从i-1递减到1，执行次数为 (i-1) 次
  for (int j = i - 1; j > 0; j--)                        // 每次外层循环i对应执行i-1次
  {
    // ElementAt(j)需要遍历j个节点，时间复杂度O(j)
    currentSum += sumSequence.ElementAt(j);              // 每次内层操作：O(j)
  }
  sumSequence.AddLast(currentSum);                       // O(1)：LinkedList.AddLast常数时间
}

内层循环总时间计算

外层循环i从2到n-1，每个i对应的内层循环总时间为：

• 当i=2时：j=1 → 总时间O(1)
• 当i=3时：j=2、1 → 总时间O(2)+O(1)
• ...
• 当i=n-1时：j=n-2、n-3...1 → 总时间O(n-2)+O(n-3)+...+O(1)

将所有内层循环时间求和，等价于计算：
$$\sum_{k=1}^{n-2} \sum_{m=1}^{k} m$$
其中k = i-1（i从2到n-1对应k从1到n-2）。

通过求和公式推导：
$$\sum_{m=1}^{k} m = \frac{k(k+1)}{2}$$
$$\sum_{k=1}^{n-2} \frac{k(k+1)}{2} = \frac{1}{2} \left( \sum_{k=1}^{n-2} k^2 + \sum_{k=1}^{n-2} k \right)$$
代入平方和与等差数列求和公式后，最高次项为$n^3$，因此这部分总时间复杂度为 O(n³)。

第二个循环（输出逻辑） #

for (int i = 0; i < sumSequence.Count(); i++)            // sumSequence.Count()为O(1)，循环执行n次（最终链表有n个元素）
{
  Console.WriteLine(sumSequence.ElementAt(i));           // 每次ElementAt(i)为O(i)，总时间为$\sum_{i=0}^{n-1} O(i) = O(n²)$
}

总复杂度推导 #

Step 1：合并所有项并移除常数 #

所有部分的时间复杂度相加：$O(1) + O(n³) + O(n²)$，移除常数项后得到 $O(n³) + O(n²)$

Step 2：移除低阶项和系数 #

由于$n³$的增长速度远快于$n²$，低阶项$O(n²)$可以忽略，得到 $O(n³)$

Step 3：选取最显著项 #

最终总时间复杂度为 O(n³)

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