嵌套循环时间复杂度疑问：为何工具判定O(n²)而非预期O(n)？

问题描述 #

我用两款免费在线Big O检查工具分析代码，它们都判定时间复杂度为O(n²)，但我认为应该是O(n)。我的主代码如下：

for (int k = 0; k < 8; k++) {
        num = hwexamples[k];
        n = Integer.parseInt(num);
        int[] room = new int[n];
        for (int j = 0; j < n; j++) {
            room[j] = i;
            i = rndm.nextInt(365);
        }
        System.out.println(duplicatecheck(room));
    }

外层循环固定执行8次迭代，我觉得不可能是O(n²)，想知道是不是有遗漏的点？

补充的duplicatecheck方法代码：

public static boolean duplicatecheck (int[] room) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < room.length; i++) {
            map.put(room[i], i);
        }
        for (int i = 0; i < room.length; i++) {
            int target = room[i];
            if (map.containsKey(target) && map.get(target) != i) {
                return true;
            }
        }
        return false;
    }

我预期时间复杂度为O(n)，请问如何优化代码提升效率？

疑问解答 #

你是对的，这段代码的时间复杂度确实是O(n)，在线工具的判定属于误判，原因如下：

• 外层循环的8次是固定常量，Big O表示法会忽略常量系数，不会影响复杂度量级。
• duplicatecheck方法里的两个for循环是独立的O(n)操作，HashMap的put、containsKey、get平均时间复杂度都是O(1)，所以整个方法的时间复杂度是O(n)。
• 主代码内层循环是O(n)，加上固定8次的外层循环，整体是O(8*n)，忽略常量后就是O(n)，和O(n²)完全不沾边。

代码优化方案 #

你的duplicatecheck方法可以大幅优化，当前写法做了两次遍历，逻辑存在冗余，优化思路如下：

1. 一次遍历完成检测 #

遍历数组时，每遇到一个元素先检查是否已存在于存储结构中：

• 若存在，直接返回true（找到重复）
• 若不存在，将元素存入存储结构
  这样无需第二次遍历，还能提前终止循环，效率更高。

优化后的代码：

public static boolean duplicatecheck(int[] room) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < room.length; i++) {
        int current = room[i];
        if (map.containsKey(current)) {
            return true;
        }
        map.put(current, i);
    }
    return false;
}

2. 用数组替代HashMap进一步优化 #

由于你的元素是0-364范围内的整数（从rndm.nextInt(365)可知），可以用固定大小的boolean数组代替HashMap，消除哈希冲突的开销，空间和时间效率都会提升：

public static boolean duplicatecheck(int[] room) {
    boolean[] seen = new boolean[365];
    for (int num : room) {
        if (seen[num]) {
            return true;
        }
        seen[num] = true;
    }
    return false;
}

这个版本时间复杂度仍为O(n)，但实际运行速度更快，空间占用也更小。

内容的提问来源于stack exchange，提问作者Matti Gebresilassie