algorithm - 考虑时间复杂度时，Theta(n) 和 T(n) 有什么区别？

Question

教授在讨论归并排序的时间复杂度，他把整个过程分为三个步骤。

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

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

这是来自 Youtube 的链接:https://www.youtube.com/watch?v=JPyuH4qXLZ0

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

Answer 1

教授所说的 T(n) 的意思是确切的复杂度，即算法需要完成的步骤数，这实际上可能因实现而异。更有趣的是 asymptotic complexity ，这里表示为 Θ(n)，显示 T 随 n 增长的速度。

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