为什么我们可以假设对于 T(n) = 2T(n/2) + theta(1)，n 是 2 的幂？
Why can we assume that for T(n) = 2T(n/2) + theta(1), n is a power of 2?
最近对算法很感兴趣，一直在看麻省理工学院发布的系列视频。不过我遇到了一些关于复发的问题。
附件link为视频来源。在07:10，教授提到由于某个定理，使用T(n/2) in T(n) = 2T(n/2) + theta(1)很好，尽管使用T（n/2的底数）或[=12会更准确=].
这个定理到底是什么？实际上我有点困惑，因为 n/2 可能不会为某些 n 生成基本情况输入。
例如一些初始输入不是 2 的 次幂。
好问题。我相信您在那节课中了解了 Big-O，所以我不会对此进行详细说明。 （我的解释会用O(N)，为了解释方便，可以假设和theta(N)一样，但它们是不同的！）
Big-O（和 theta）的重要部分是 SIGNIFICANCE。例如，O(N) 总是比 O(1) 更重要，即使它是 99999*O(1) vs O(N)。
所以，您的教授想说的是，当您执行 n/2 时，您不必限制或限制它，因为您取消的额外部分不是 显着。您正在处理的是 Big-O 场景中的运行时，它不关心细节。我们假设 N 是 HUGE，并且您花在尝试下限或上限 N 上的一点点额外时间永远无法比较。
基本上对于 Big-O，您需要全面概括，幸运的是这意味着您可以假设 n 是 2 的幂！
最近对算法很感兴趣，一直在看麻省理工学院发布的系列视频。不过我遇到了一些关于复发的问题。
附件link为视频来源。在07:10，教授提到由于某个定理，使用T(n/2) in T(n) = 2T(n/2) + theta(1)很好，尽管使用T（n/2的底数）或[=12会更准确=].
这个定理到底是什么？实际上我有点困惑，因为 n/2 可能不会为某些 n 生成基本情况输入。
例如一些初始输入不是 2 的 次幂。
好问题。我相信您在那节课中了解了 Big-O，所以我不会对此进行详细说明。 （我的解释会用O(N)，为了解释方便，可以假设和theta(N)一样，但它们是不同的！）
Big-O（和 theta）的重要部分是 SIGNIFICANCE。例如，O(N) 总是比 O(1) 更重要，即使它是 99999*O(1) vs O(N)。
所以，您的教授想说的是，当您执行 n/2 时，您不必限制或限制它，因为您取消的额外部分不是 显着。您正在处理的是 Big-O 场景中的运行时，它不关心细节。我们假设 N 是 HUGE，并且您花在尝试下限或上限 N 上的一点点额外时间永远无法比较。
基本上对于 Big-O，您需要全面概括，幸运的是这意味着您可以假设 n 是 2 的幂！