对两个数组进行排序的时间复杂度

在 O 表示法中，变量 n 表示问题的“大小”。例如，如果你有一个包含 10 个元素的列表，并且想要对其进行排序，则问题的大小为 10。对于两个数组，我们有两个问题大小，n 和 m。因此复杂度为 O（nlog（n）） + O（mlog（m）），这与 O（nlog（n） + mlog（m）） 相同。

n 表示较大数组的大小。

首先，回想一下 Big-O 的含义：当且仅当存在某个常数 M 使得 k（n） < M * n log（n） 对于所有大于某个大小的 n，函数 k 是 O（n log（n））。

现在，在这种情况下，函数 k 是什么？它是对两个数组进行排序的程序的运行时。以这种方式重新表述上面对Big-O的定义，我们看到“时间复杂度为O（n log（n）））”这句话等价于句子

“给定大小 n 的运行时不超过 （n log n） 的常数倍数。”

因此，我们尝试根据 n 来限制运行时的大小。什么是n？

好吧，n 不能是较小数组的大小，因为较小数组的大小不会对运行时所依赖的较大数组的大小设置上限。也就是说，即使我们知道较小数组的大小很小（例如，1 个元素），这并不能阻止较大数组的大小变得巨大（例如，995,566,214,678 个元素），因此仅较小的数组的大小不能对总运行时间设置上限。

现在，如果我们让 n 成为更大数组的大小呢——这能解决我们的问题吗？

一句话，是的。

这是因为较小数组的大小小于较大数组的大小，因此较大数组的大小确实限制了较小数组的大小，因此它也限制了总运行时。