递归实现格雷码算法的时间复杂度该如何估算？

下界判断正确性 #

你的判断完全正确。n位格雷码的序列长度固定为2^n，每个元素至少需要执行一次写入结果列表、加入历史哈希集合的操作，单操作开销为常数级，因此时间复杂度的下界必然是Ω(2^n)。

时间复杂度上界计算 #

你提到的回溯因素可以结合算法逻辑和n维超立方体的特性推导：

• 该问题本质是在n维超立方体上寻找哈密顿回路：超立方体的每个节点对应一个n位二进制数，边连接所有仅相差1比特的节点，每个节点的度数为n。
• 算法从序列最后一个节点出发，逐位翻转尝试未访问的邻居节点，走通则直接向上返回结果，走不通就回溯移除节点，不会做多余的遍历。
• 历史哈希集合的查询、插入、删除操作平均复杂度为O(1)，每一层递归的循环最多执行n次，单轮递归的开销为O(n)。
• 最坏情况下，每个节点最多会被尝试n次（从不同的前驱节点访问），但由于格雷码存在确定性的合法解，算法找到第一个合法序列后就会立刻终止所有递归，不会遍历所有可能的路径，因此总递归调用次数的上界为O(n*2^n)，对应整体时间复杂度上界为O(n*2^n)。
• 实际运行中该算法的回溯次数极少，运行效率非常接近上述上界，不会出现额外的指数级回溯开销。

参考算法实现 #

public static List<Integer> grayCode(int numBits) {
    List<Integer> result = new ArrayList<>(List.of(0));
    directedGrayCode(numBits, new HashSet<Integer>(List.of(0)), result);
    return result;
}

private static boolean directedGrayCode(int numBits, Set<Integer> history, List<Integer> result) {
    if (result.size() == (1 << numBits)) {
        return differsByOneBit(result.get(0), result.get(result.size() - 1));
    }

    for (int i = 0; i < numBits; ++i) {
        int previousCode = result.get(result.size() - 1);
        int candidateNextCode = previousCode ^ (1 << i);
        if (!history.contains(candidateNextCode)) {
            history.add(candidateNextCode);
            result.add(candidateNextCode);
            if (directedGrayCode(numBits, history, result)) {
                return true;
            }
            result.remove(result.size() - 1);
            history.remove(candidateNextCode);
        }
    }
    return false;
}

private static boolean differsByOneBit(int x, int y) {
    int bitDifference = x ^ y;
    return bitDifference != 0 && (bitDifference & (bitDifference - 1)) == 0;
}

内容的提问来源于stack exchange，提问作者super.t