求解生成数组所有唯一数对的代码时间复杂度

架构老林

2026-5-22

生成唯一数对解法的时间复杂度分析

给定一个数字数组，生成所有唯一数对。例如，给定数组[1,2,3,4,5]，唯一数对为：(1,2)、(1,3)、(1,4)、(1,5)、(2,3)、(2,4)、(2,5)、(3,4)、(3,5)、(4,5)。
给出的解法代码如下：
int[] numbers = new int[] { 1, 2, 3, 4, 5 };
HashSet<Pair> pairs = new HashSet<Pair>();
for(int i = 0; i < numbers.Length; i++) {
    for(int j = i + 1; j < numbers.Length; j++) { // 修正原代码的语法错误：将逗号改为分号
        pairs.Add(new Pair(numbers[i], numbers[j]));
    }
}
请问该解法的时间复杂度是多少？

咱们一步拆解这个解法的时间复杂度：

循环执行次数
外层循环i从0到n-1（n为数组长度），内层循环j每次从i+1开始遍历到数组末尾。总循环次数是组合数C(n,2)，也就是n*(n-1)/2，这个数量级属于O(n²)——当n足够大时，低阶项和常数项可以忽略不计。
HashSet.Add操作的时间
假设Pair类正确实现了Equals()和GetHashCode()方法（这是HashSet正常去重的前提），那么HashSet.Add()的平均时间复杂度是O(1)，因为哈希表的插入操作在无冲突或冲突极少的情况下是常数时间。
整体时间复杂度
把两部分结合起来，总时间就是循环次数乘以每次循环内的操作时间，也就是O(n²) * O(1) = O(n²)。