我正在学习大 O 符号，我有点困惑。我不认为我真的了解“复杂性”对算法的影响，而且我不知道我是否在向后看。
复杂度的顺序是从最小到最复杂：O(1)、O(log n)、O(n)、O(n log n)、O(n^2)？还是我把它弄反了？
如果这是正确的顺序，我猜一个复杂度为 O(n^2) 的程序会比 O(n log n) 的程序更快地处理大量数据。然而，在测试了冒泡排序（O（n^2））和快速排序（O（n log n））之后，很明显O（n ^ 2）排序的处理速度比O（n log n）慢得多。所以我很困惑......复杂性是好是坏？如果算法更复杂，算法会很快（就完成程序需要多长时间而言），还是复杂的程序会更慢？
O 表示法表示计算机将对具有算法将处理的对象的最大元素数进行的数字操作。例如，如果您使用具有 O(n^2) 的算法对具有 3 个元素的数组进行排序，这意味着计算机将对数组执行最多9 次操作。
在这里，您可以查看不同 O 复杂度之间的比较：
要回答您的第一个问题，是的，这是正确的复杂顺序。大 O 表示法不会告诉您程序或算法需要多长时间才能运行。它只是相对于具有更好复杂性或更差复杂性的另一种方法来衡量其性能。为了帮助您对其进行概念化，O(1)将是一条指令，O(n)将是一个单循环，O(n^2)将是一个内部带有嵌套循环的循环。
要回答您关于O(n^2)比O(n log n)快的问题，它可能不会。我说可能是因为有许多因素决定了程序的速度，并且可以想象，复杂性更差的程序比复杂性更高的程序执行得更快。换句话说，大 O 表示法衡量算法的复杂性，而不是构成该算法的程序。
例如，假设您有两个程序，为简单起见，一个在O(n)时间内运行，另一个在O(n^2)时间内运行。
运行 10 个对象，具有O(n)时间的程序导致 100 毫秒。以O(n^2)时间运行程序会导致 10 毫秒。这是为什么？因为与第一个程序相比，执行工作所需的时间为 O(n^2)的程序少。
但是让我们看看 100 个对象会发生什么。具有O(n)时间的程序会产生 1000 毫秒，而具有O(n^2)时间的程序也会产生 1000 毫秒。对于较大的对象，它的增长速度要快得多，这就是为什么一般来说，优化复杂性会更好。
有些算法的复杂度无法降低，例如旅行商问题的变体，它询问是否存在一定长度的路径来通过他必须访问的所有城市。要获得有保证的最佳解决方案，您必须运行所有可能的场景，其中包含O(n!)的大 O 表示法，这已经非常糟糕了。幸运的是，有许多替代算法可以确定 98% 以内的解决方案，并且可以更快地执行。在O(n!)时间内运行的一组已知问题称为NP 问题。
我希望这能回答你的问题。