这是我想出的一个算法片段：
for (int i = 0; i < n - 1; i++)
for (int j = i; j < n; j++)
(...)
n + (n-1) + (n-2) + ... + 1 = sum from 1 to n = (n (n - 1))/2
以下是我感到困惑的地方：
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
(...)
O(n²)，但它明显（最坏情况下）比第一个更好。我错过了什么？这个信息准确吗？有人能解释一下这个“现象”吗？(n (n - 1))/2 简化为 n²/2 - n/2。如果你使用非常大的数来代替 n，那么 n/2 的增长速度将相对于 n² 被忽略不计，在计算大O复杂度时你可以有效地忽略它。同样，常量值 1/2 不会随着 n 的增加而增长，所以也可以忽略它。这就只剩下 n²。
只要记住，复杂度计算与“速度”并不相同。一种算法可能比另一种慢五千倍，但仍然具有更小的大O复杂度。但是，随着 n 增大到非常大的数字，通常会出现一般模式，可以使用简单的公式进行分类: 1、log n、n、n log n、n²等。
有时候创建一个图表并观察出现的线条类型有帮助：
即使这两张图的缩放因子非常不同，你也可以看到它产生的曲线类型几乎完全相同。
n^2 - n/2 算法没有任何理由优于第二个 n^2 算法，对吧？ - Werner常数因子。
大O符号忽略常数因子，所以即使第二个循环比第一个慢一个常数因子，它们最终的时间复杂度相同。
在定义中，它告诉你可以选择任何旧的常数因子:
……当且仅当存在正常数M……
这是因为我们想要分析算法的增长率-常数因子只会使事情变得复杂，并且通常是系统相关的（在不同的机器上操作可能持续不同的时间）。
您可以只计算某些类型的操作，但问题在于选择哪种操作，如果该操作在某些算法中不占主导地位怎么办。然后，您将需要以一种相互关联的方式来比较操作（以系统无关的方式，这可能是不可能的），或者您可以只为每个操作分配相同的权重，但这将是相当不准确的，因为有些操作会比其他操作花费更长的时间。
说出 O(15n² + 568n + 8 log n + 23 sqrt(n) + 17)（例如）有多有用？与仅使用 O(n²) 相比。
（为了下面的目的，假设 n >= 2）
请注意，这里实际上有渐近更小的项（即当我们接近无穷大时更小），但我们始终可以将其简化为常数因子的问题。（它是n(n+1)/2，而不是n(n-1)/2）
n(n+1)/2 = n²/2 + n/2
and
n²/2 <= n²/2 + n/2 <= n²
n² - n < 2n²。 - Bernhard Barker在典型的用法中，不直接使用O符号的正式定义；相反，通过以下简化规则导出函数f的O符号：
如果f(x)是几个项的总和，则保留增长率最大的一项，并省略所有其他项
大O符号仅用于给出渐近行为 - 其中一个比另一个快一点并不重要 - 它们都是O(N^2)
你也可以说第一个循环是 O(n(n-1)/2)。大O的花式数学定义是：
如果存在常量c和n，使得对于某些c和所有x > n，f(x) < c*g(x)，则函数"f"是函数"g"的大O。
这是一种说法，即在某一点之后，g是一个上界，加上一些常数。因此，O(n(n-1)/2) = O((n^2-n)/2)是O(n^2)的大O，这更方便快速分析。
据我所知，你的第二段代码片段
for(int i = 0; i < n; i++) <-- this loop goes for n times
for(int j = 0; j < n; j++) <-- loop also goes for n times
(...)
因此，它的时间复杂度是O(n*n) = O(n^2)。
根据BIG-O理论，会忽略常数因子，只考虑更高阶的影响。也就是说，如果复杂度为O(n^2+k)，那么实际复杂度将是O(n^2)，常数k将被忽略。
或者，如果复杂度是O(n^2+n)，则实际复杂度将是O(n^2)，低阶的n将被忽略。
因此，在你的第一个情况下，复杂度为O(n(n - 1)/2)可以简化为
O(n^2/2 - n/2) = O(n^2/2) (Ignoring the lower order n/2)
= O(1/2 * n^2)
= O(n^2) (Ignoring the constant factor 1/2)