如何正确计算for循环的Big-O时间复杂度？ (C#)

Question

我正在研究如何正确计算大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 + 1
    {
    int currentSum = 0;                                      // n
    for (int j = i - 1; j > 0; j--)                          // n^2 + 1
    {
        currentSum += sumSequence.ElementAt(j);              // n^2
    }                                                           
    sumSequence.AddLast(currentSum);                         // n
    }

    for (int i = 0; i < sumSequence.Count(); i++)            // n + 1
    {
    Console.WriteLine(sumSequence.ElementAt(i));             // n
    }
    //-------------
    // Total:
    // 2n^2 + 5n + 7
    // 2n^2 +5n     <-- Clear constant terms
    // n^2 + n      <-- Clear coeffients
    // n^2          <-- Pick most signification term.

我相当认为整体时间复杂度是 Big O(n^2)，尽管我不确定我是否正确计算了内部和外部 for 循环。

CodePal.ai 说道：

外环：

(int i = 2; i < n; i++)

的外层循环运行了

n - 2

次，所以它的时间复杂度是

O(n)

。

内循环：

(int j = i - 1; j > 0; j--)

的内部循环对于外部循环的每次迭代运行

i - 1

次。内循环的迭代总数是前

n - 2

自然数之和，等于

(n-2)(n-1)/2

。因此，内循环的时间复杂度为

O(n^2)

。

那么...我应该将这些行更改为等于

n - 2

，如果是的话 - 你能解释一下为什么吗？我认为所有 for 循环都相等

n + 1

非常感谢大家，真的很感激！

Answer 1

那么...我应该将这些行更改为等于 n - 2，如果是这样 - 你能解释一下为什么吗？我认为所有 for 循环都等于 n + 1

您的问题是为什么从

for

到

2

的

n - 1

循环会运行

n - 2

次？这是基础数学，

n - 1 - 2 + 1 = n - 2

。

我应该改变吗

你的侧面曲线并不重要，只有最重要的多项式因子才重要。无论您从何处开始循环，

O(n)

都是

O(n)

。

也就是说，您的大部分分析都是错误的。您使用的是最糟糕的集合（链表），并且

ElementAt()

和

Count()

都是线性的，而不是常数。这使得第一个嵌套循环

O(n^3)

和第二个

O(n^2)

。除了时间复杂度之外，你还有很多东西需要学习。