面试题库 › C++ / 后端 › 全排列回溯算法的时间复杂度和空间复杂度是多少?

全排列回溯算法的时间复杂度和空间复杂度是多少?

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:复杂度分析

哪些公司问过

字节跳动1华为1微软1

常见岗位:软件开发、C/C++ 软件开发、软件开发(未写技术栈)

答案要点

  1. 共 n! 个排列,每个复制 O(n),时间 O(n×n!)
  2. 递归树内部节点总数约 e×n!,每节点循环 n 次,量级一致
  3. 不计输出空间为 O(n):递归深度 n,加 path 和 visited
  4. 计入结果集则空间 O(n×n!)
  5. 交换法省去 visited;有重复元素先排序再同层剪枝

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题