搜索与排序算法中Big O符号赋值规则及归并排序等复杂度疑问

一、插入排序时间复杂度确认 #

你的结论是对的：插入排序的最坏和平均时间复杂度确实是O(n²)，不过你的理解细节有点偏差——插入排序并不是“寻找最小值”，它的逻辑是：从第二个元素开始，把当前元素向前插入到前面已排序序列中的正确位置。比如处理第i个元素时，最多需要和前面i个元素逐一比较并移动，总操作数是1+2+...+(n-1) = n(n-1)/2，对应O(n²)的复杂度。当然如果数组已经是有序的，插入排序只需要遍历一次，时间复杂度是O(n)（最好情况）。

二、归并排序时间复杂度解析：为什么是O(n log n) #

归并排序是典型的分治算法，拆分和合并两个阶段决定了它的复杂度：

1. 拆分阶段：每次把数组对半拆分，直到每个子数组只有1个元素。这个过程的层数是log₂n——比如n=8时，拆分成[4,4]→[2,2,2,2]→[1,1,...1]，一共3层，而log₂(8)=3；n=16时就是4层，以此类推。不管n是多少，拆分的总层数都是log n（底数不影响Big O的表示，所以写成log n）。
2. 合并阶段：每一层的所有子数组合并时，总操作数都是O(n)。因为每一层的所有子数组加起来正好是原数组的n个元素，合并两个有序数组的操作数等于两个数组的元素总数，所以每一层合并的总耗时都是线性的O(n)。

把两个阶段结合起来：总操作数 = 层数 × 每层操作数 = n × log n，所以时间复杂度是O(n log n)。举个具体例子：n=8时，3层×8个元素/层=24次核心操作，对应8×log₂(8)=24，完全匹配。

三、时间复杂度通用理解建议 #

• 抓核心：操作次数的增长趋势。Big O描述的是当数据量n趋近于无穷大时，算法操作次数的增长速率，不用纠结具体的常数或低阶项（比如n(n-1)/2直接简化为O(n²)）。
• 分治算法看“层数×每层操作”：像归并排序、快速排序这类分治算法，先算拆分的层数（通常是log n，因为每次对半分），再算每层需要处理的元素总数，两者相乘就是总复杂度。
• 嵌套循环对应幂次：如果算法是两层嵌套循环（比如冒泡排序的外层遍历数组，内层比较相邻元素；插入排序的外层遍历，内层向前比较），且每层循环的操作次数都和n正相关，那复杂度就是O(n²)；单层循环就是O(n)。
• 区分三种情况：很多算法的最好、最坏、平均复杂度不同，比如插入排序最好O(n)、最坏O(n²)，而归并排序三种情况都是O(n log n)，分析时要明确是哪种场景下的复杂度。

内容的提问来源于stack exchange，提问作者David Huang