在考虑时间复杂性时，Theta(n)和T(n)有什么区别？

Question

教授正在讨论合并排序的时间复杂性，他将整个过程分为三个步骤。

1. 检查数组的大小是否为1 ->时间复杂度: theta(1)
2. 他描述了->时间复杂度: 2T(n/2)的排序过程。
3. 合并两个排序序列->时间复杂度: theta(n)

我不明白第二步，为什么他把它描述为2T(n/ 2 )而不是2 2Theta(n/2)？θ(N)和T(n)有什么区别？

以下是Youtube的链接：https://www.youtube.com/watch?v=JPyuH4qXLZ0

在1:08:45 - 1:10:33之间

Answer 1

教授所说的T(n)的含义是精确的复杂性，即算法需要完成的步骤数，实际上，这可能因实现的不同而有所不同。更有趣的是渐近复杂性，这里表示为Θ(n)，它展示了T与n一起增长的速度。

合并算法的第一步是将数组分成两半，并使用相同的算法(因此是递归的)对每一半进行排序。这一步显然采取了2T(n/2)。然后合并两个部分(因此得名)，这需要线性时间，Θ(n)。从递归定义T(n) = 2T(n/2) + Θ(n)导出了T(n) = Θ(nlogn)，这是合并算法的复杂性类。