我在很多地方都看到合并2 n个大小的排序数组的时间复杂度是O（n）。 Θ（n）在这里不准确吗？
提前致谢！
证明Θ（f（x））比证明O（f（x））更困难，所以很多人都不打扰。然而，在这种情况下，就地合并两个n大小的排序列表实际上是正确的，对于所有可能的输入而言是O（n）而不是Θ（n）。
显然，复制合并两个n大小的列表不能比O（n）更好，因为正在复制2 * n个元素。但是，就最佳情况场景而言，可以在Ω（1）中实现就地合并。当第一个列表的所有元素都小于或等于第二个列表中的元素时，这是一个简单的情况。合并算法可以在O（1）中检测到这种情况，如果元素已经处于正确的顺序则不执行任何操作，因此Ω（1）表示最佳情况。
结论：就地合并不是Θ（n），而是Ω（1）。实际上，与额外内存的就地合并可以是Ω（1）和O（n），但是如果没有额外的内存，则需要O（n log n）来合并两个n大小的列表，所以显然问题不在于这种情况。
这就是为什么说O（n）更简单，并且不会受到就地与复制合并的细节的困扰。而且，通常困扰程序员的是最糟糕的情况，而且通常情况下，不是最好的情况。
在许多情况下，当人们说O（f（n））时，他们的意思是Θ（f（n））最坏情况的复杂性。就最坏的情况而言，就地合并也是Θ（n），就像复制合并一样。
当人们谈论复杂性时，人们通常会提到所有可能的运行。如果最坏的情况是Θ（f（x））并且最好的情况是Θ（g（x）），那么在技术上正确写O（f（x））和Ω（g（x））对于所有人都是紧的可能的情况。
类似地，如果复制数组是Θ（n），则没有任何意义说它是O（2n）。这在技术上是正确的，但是大O符号的使用非常罕见。