我的气泡排序代码的时间复杂度是否正确

Question

计算机科学新手，所以我写了这个气泡排序代码，并试图在这里计算它的时间复杂度和性能，排序的代码在这里：

for (int i = 0; i < size; i++)
{
  Node current = head.next;
  while (current.next != tail)
  {
    if (current.element.depth < current.next.element.depth)
    {
      swap(current, current.next);
    }
    else
    {
      current = current.next;
    }
  }
}

交换方法代码在这里：

void swap(Node nodeA, Node nodeB)
{
    Node before = nodeA.prev;
    Node after = nodeB.next;
    before.next = nodeB;
    after.prev = nodeA;
    nodeB.next = nodeA;
    nodeB.prev = before;
    nodeA.prev = nodeB;
    nodeA.next = after;
}

现在我知道气泡排序的时间复杂度在最坏情况下的性能O(n^2)，但我在这里尝试计算 for 循环中每个执行的函数。我对时间复杂度有基本的了解，我知道循环的标准是f(n) = 2n + 2，我们考虑时间复杂度的最坏情况。到目前为止，这是我为我的代码找到f(n)的思想进展：

int i = 0;            This will be executed only once.
i < size;             This will be executed N+1 times.
i ++;                 This will be executed N times.
current = head.next;  This will be executed N times.
current.next != tail; This will be executed N times.
And since a while loop is within the for loop,
    it's n*n within the while loop, there
    are 4 operations, so it's 4n^2.

在最坏的情况下，我每次都必须使用 swap 方法，而且由于我对 swap 方法的时间复杂度只是8（我认为，它只是8执行吧？所以对swap(current,current.next)来说最糟糕的情况是8n？

如果我们将它们加起来：

f(n) = 1 + n + 1 + n + n + n+  4n^2 + 8n
f(n) = 4n^2 + 12n + 2
f(n) ~ O(n^2)

我的时间复杂度f(n)正确吗？

如果没有，你能指出我正确的答案吗，你也有一些建议来提高我的代码性能吗？

Answer 1

由于你在 for 循环中有一个 while 循环 - 是的，你有一个 O（n^2） 的复杂性，这被认为是不好的。

这里的经验法则如下（对于N个元素输入，从好到坏）：

• 没有循环，只有一些执行，无论输入大小如何 = O（1）
• 循环（N/M）（每次迭代时除以输入）= O（log N）
• 只需在 N 个元素上循环一次 = O（N）
Loop2（N）
• 在 Loop1（N） = O（N^2）

请参阅此答案以获得更好的解释：O（log n）到底是什么意思？