此代码片段 (c#) 的 O 复杂性大吗？

Question

我是一名计算机科学学生，我需要计算以下 C# 代码的 Big O 时间复杂度，并展示我对每一行的思考过程（如我在右侧的注释所示）：

int n = Int32.Parse(Console.ReadLine());                 // 1

LinkedList<int> sumSequence = new LinkedList <int>();    // 1

sumSequence.AddLast(0);                                  // 1
sumSequence.AddLast(1);                                  // 1

for (int i = 2; i < n; i++)                              // n - 2
{
  int currentSum = 0;                                    // 1

  for (int j = i - 1; j > 0; j--)                        // ??
  {
    currentSum += sumSequence.ElementAt(j);              // ??
  }
  sumSequence.AddLast(currentSum);                       // ??
}

for (int i = 0; i < sumSequence.Count(); i++)            // ??
{
  Console.WriteLine(sumSequence.ElementAt(i));           // ??
}

// Total:
// Step 1: XXX  <- Remove constants
// Step 2: XXX  <- Remove coefficients
// Step 3: XXX  <- Select most prominent

我的问题是，我可以逐行计算 Big O，直到到达内部 for 循环（我放置“??”的位置）。

事实上还有一个

.ElementAt()

方法（我知道是 O(n) ），这让我更加困惑。

有人可以帮我解决这个问题吗？我将永远感激并承诺将其转发出去。

谢谢！

• 卢克

Answer 1

好吧，如果您正在寻找

O

，而不是确切的操作次数：

int n = Int32.Parse(Console.ReadLine());                 // O(1)

LinkedList<int> sumSequence = new LinkedList <int>();    // O(1)

sumSequence.AddLast(0);                                  // O(1)
sumSequence.AddLast(1);                                  // O(1)

for (int i = 2; i < n; i++)                              // O(n)
{
  int currentSum = 0;                                    // O(n)

  for (int j = i - 1; j > 0; j--)                        // O(n^2)
  {
    currentSum += sumSequence.ElementAt(j);              // O(n^3)
  }

  sumSequence.AddLast(currentSum);                       // O(n)
}

for (int i = 0; i < sumSequence.Count(); i++)            // O(n)
{
  Console.WriteLine(sumSequence.ElementAt(i));           // O(n^2)
}

最终整体时间复杂度为

O(n^3)