如果最后一次交互被忽略，为什么泡泡的大 O 排序为四进制时间?

Question

>我有以下气泡排序算法：

public void BubbleSort(int[] arr, int start, int end)
{
int instructions = 0;
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i = 0; i < arr.Length - 1; i++)
{
//instructions++;
for (int j = i + 1; j < arr.Length; j++)
{
instructions++;
if (arr[i] > arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
swapped = true;
}
}
}
}
Console.WriteLine("instructions++ " + instructions);
}

如果你打印instructions你会看到它完全是：(n^2( - n

那么我们为什么要忽略-n呢？

即使它对输入大小是可变的，它是否被认为是常量(买嘿..(会很奇怪？

Answer 1

时间强制性就是这样工作的。在这种情况下，对于较大的 n 值，线性 n 无关紧要。例如，如果我们谈论的是 1000 万个数字，则值 (10^6(^2 远远大于 10^6。因此，即使它存在，另一个因素也使大 n 相形见绌，因此更容易忽略它。