面试题库 › C++ / 后端 › 归并排序及其时间复杂度推导

归并排序及其时间复杂度推导

难度 ★☆☆在 1 场真实面经中被问到 方向:C++ / 后端考点:排序算法

哪些公司问过

拼多多1

常见岗位:C/C++ 软件开发

答案要点

  1. 分治:对半拆分、递归排序、合并两个有序子数组
  2. 合并用双指针,相等时取左侧元素,保证稳定
  3. 递推式 T(n)=2T(n/2)+O(n)
  4. 递归树共 log n 层,每层合并总代价 O(n),总计 O(n log n)
  5. 最好最坏平均均为 O(n log n),额外空间 O(n)

易错点

面试官常见追问

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

相关面试题