关于O(n log n)与O(m)复杂度算法组合的判定及条件问询

当你将分别处理集合A（复杂度O(n log n)）和集合B（复杂度O(m)）的两个算法结合时，整体时间复杂度由两者中增长速度更快的那个决定，即：

整体复杂度 = O(max(n log n, m))

整体复杂度为O(m)的条件 #

要让组合后的复杂度退化为O(m)，核心是让O(n log n)的增长速度不超过O(m)，具体需满足：

• 存在固定常数c>0，当n足够大时，n log n ≤ c * m
• 常见的满足关系包括：
  • m的增长阶数高于或等于n log n，比如m = Ω(n log n)（例如m = n log n、m = n²等）
  • n是固定不变的常数（此时n log n为常数项，不会随输入规模增长，整体复杂度由O(m)主导）

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