对于配对操作，我很难理解大 O 符号。问题很简单——为数组中给定的数字列表生成所有可能的对。
我的第一个猜测是有一个嵌套的 for/foreach 循环并生成对。这很容易，我得到每个 n，我分析 n 个其他数字，这给了我 n^2 的复杂性。
现在，如果我尝试进一步优化它并说 (1,4) 与 (4,1) 相同，那么对于像 1,2,3,4,5 这样的排序数组。我只以这种方式在嵌套的 for 循环中运行配对操作
for (i =0; i < count; i++) {
for (j = i + 1; j < count - 1; j++)
}
}
在这种情况下，我只运行数组 < n^2 次。对于 7 个数字的样本大小，我运行循环 21 次以生成对。我知道这不可能是一个 log-n 运算，我很想说这个运算收敛到 n^2，但我从我的数学或理论课上记不住足够明确地回答这个问题。我该如何解决这个问题？
背景：我接受了一个类似问题的采访，这源于我和朋友的一次争论，如果一个列表中的配对操作可以比 n^2 更好。
您是正确的，您执行的操作少于 n 2 次。问题是你做的操作少了多少。
让我们考虑一下数组中有多少对。如果 n 个数字中的每一个都可以与 (n - 1) 个其他数字配对，则可能的配对总数为 n(n - 1)。原始 for 循环的每次迭代都会生成这些对中的一个，因此您生成的对的总数为 n 2 - n，即 O(n 2 )。
现在，如果您通过说 (1, 4) 和 (4, 1) 相同来消除重复对呢？在这种情况下，请注意您生成的一半对将是无关的 - 您将生成每对两次。这意味着对的数量是 (n 2 - n) / 2。这个表达式小于 n 2，但请注意它仍然是 O(n 2 )，因为 big-O 表示法忽略了常量。
换句话说 - 您生成的对数少于 n 2对是对的，但您正在创建的对数总数仍然是 O(n 2 )。
更一般地说 - 如果您曾经将算法所做的工作总量减少了某个常数因子（例如，您将工作量减少了一半，或者将工作量减少了 100 倍），那么您并没有改变 big-O 运行时的算法。Big-O 完全忽略常量。为了减少 big-O 运行时间，您需要将总工作量减少一个大于常数的量；比如说，乘以 n、log n 等因子。
希望这可以帮助！
请记住，大 O 表示法涉及隐含的乘法常数。因此，如果您的运行时间 <= kn^2 as n -> infinity，您的复杂性仍然是 O(n^2)。
它仍然是 O(n^2)，因为现在您拥有的对数正好是引入订单要求之前的一半。除以二不会改变大 O。