考虑时间复杂度时，Theta(n) 和 T(n) 有什么区别？
What's the difference between Theta(n) and T(n) when considering time complexity?
教授在讨论归并排序的时间复杂度，他把整个过程分为三个步骤。
- 检查数组大小是否为1 -> 时间复杂度：theta(1)
- 他描述了排序过程->时间复杂度：2T(n/2)
- 合并两个排序序列 -> 时间复杂度：theta(n)
我不明白第2步，为什么他把它描述为2T(n/2)而不是2Theta(n/2)？ theta(n) 和 T(n) 有什么区别？
这是来自 Youtube 的 link：https://www.youtube.com/watch?v=JPyuH4qXLZ0
并且在 1:08:45 - 1:10:33
之间
教授所说的 T(n) 的意思是确切的复杂度，即算法需要完成的步骤数，这实际上可能因实现而异。更有趣的是 asymptotic complexity，在这里表示为 Θ(n)，它显示了 T 与 n 一起增长的速度。
mergesort算法的第一步是将数组分成两半，并用相同的算法对每一半进行排序（因此是递归的）。这一步显然需要 2T(n/2)。然后你合并两半（因此得名），这需要线性时间，Θ(n)。从那个递归定义 T(n) = 2T(n/2) + Θ(n) 他推导出 T(n) = Θ(nlogn) 这是合并排序算法的复杂度 class。
教授在讨论归并排序的时间复杂度，他把整个过程分为三个步骤。
- 检查数组大小是否为1 -> 时间复杂度：theta(1)
- 他描述了排序过程->时间复杂度：2T(n/2)
- 合并两个排序序列 -> 时间复杂度：theta(n)
我不明白第2步，为什么他把它描述为2T(n/2)而不是2Theta(n/2)？ theta(n) 和 T(n) 有什么区别？
这是来自 Youtube 的 link：https://www.youtube.com/watch?v=JPyuH4qXLZ0
并且在 1:08:45 - 1:10:33
之间教授所说的 T(n) 的意思是确切的复杂度，即算法需要完成的步骤数，这实际上可能因实现而异。更有趣的是 asymptotic complexity，在这里表示为 Θ(n)，它显示了 T 与 n 一起增长的速度。
mergesort算法的第一步是将数组分成两半，并用相同的算法对每一半进行排序（因此是递归的）。这一步显然需要 2T(n/2)。然后你合并两半（因此得名），这需要线性时间，Θ(n)。从那个递归定义 T(n) = 2T(n/2) + Θ(n) 他推导出 T(n) = Θ(nlogn) 这是合并排序算法的复杂度 class。