时间复杂度为O(n² log n)的算法有哪些？实现思路是什么？

你的猜想是否正确 #

你的猜想基本正确，这是绝大多数O(n² log n)算法的典型构成逻辑：

• 两层嵌套的循环各执行n次，累计时间复杂度为O(n²)
• 内层循环内部执行的操作（比如平衡树查询更新、堆操作、二分查找等）时间复杂度为O(log n)
  两者相乘后总时间复杂度就是O(n² log n)。
  当然存在少量非典型的构成场景，比如先执行一次O(n²)的预处理，后续执行总复杂度O(n log n)的查询操作，总复杂度也属于该量级，但这类场景占比很低。

常见O(n² log n)算法实例 #

• 部分增量构造实现的三维凸包算法：每插入一个新的三维点，需要遍历所有现有面判断冲突关系，同时涉及面的排序、查找操作，时间复杂度上界为O(n² log n)
• 带拓展需求的最长上升子序列相关算法：比如统计所有可重最长上升子序列的不同种类数，两层循环遍历元素对，内层用树状数组/线段树做前缀和的查询与更新，单次操作复杂度O(log n)，总复杂度为O(n² log n)
• 稠密图的特殊路径计算：比如统计所有节点对之间的次短路径长度，部分实现中两层循环遍历节点，内层用堆优化的路径搜索做相关统计，总复杂度为O(n² log n)
• 子数组属性统计类算法：需要枚举所有可能的子数组（外层枚举左端点O(n)，内层枚举右端点O(n)），每加入一个元素时用平衡树/堆维护当前子数组的中位数、第k大值等属性，单次插入查询复杂度O(log n)，总复杂度为O(n² log n)
• 字符串匹配类拓展算法：枚举所有待匹配的子串，内层用二分查找在预处理的字典树/后缀数组中做匹配查询，总复杂度为O(n² log n)

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