为什么我们假设对于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?
问题描述
最近，我对算法感兴趣，并且一直在观看MIT发布的视频系列.我遇到了一些有关复发的问题.
Lately I have been interested in algorithms and I have been watching a video series published by MIT. I encountered some problems regarding recurrence though.
附件链接是视频的来源.教授在07:10提到，尽管有一定的定理，但使用T(n/2) in T(n) = 2T(n/2) + theta(1)很好，尽管使用T(n/2的底数)或T(the ceiling of n/2)会更准确.
The attached link is the source of the video. At 07:10, the professor mentioned that it's fine to use T(n/2) in T(n) = 2T(n/2) + theta(1) due to a certain theorem, despite that it would be more accurate to use T(the floor of n/2) or T(the ceiling of n/2).
这个定理到底是什么?实际上，我有点困惑，因为n/2可能不会为某些n生成基例输入.
What exactly is this theorem? Actually I'm kind of confused because n/2 might not generate the base case input for some n.
例如一些不是 2的幂的初始输入.
e.g. some initial input that is not a power of 2.
推荐答案
好问题.我敢肯定，您在该课程中了解到Big-O，所以我不会在此赘述. (我的解释将使用O(N)，为了便于说明，可以假设O(N)与theta(N)相同，但是它们是不同的！)
Great question. I'm sure you learnt about the Big-O in that lesson, so I shall not elaborate on that. (My explanation will use O(N) which for the ease of explanation, can be assumed as the same as theta(N), but they are different!)
Big-O(和theta)的重要部分是 SIGNIFICANCE .例如，即使O(N)的值为99999 * O(1)对O(N)，也总是比O(1)高.
The important part of Big-O (and theta) is SIGNIFICANCE. For example, O(N) will always be more significant than O(1), even if it was 99999*O(1) vs O(N).
因此，您的教授想说的是，当您执行n/2时，您不必将其下限或上限，因为您消除的多余部分不是重要的.您要处理的是Big-O场景中的运行时，它并不关心细节问题.我们假设N为 HUGE (巨大)，而您花在设置N上或下限N上的额外时间是无法比拟的.
So, what your professor is trying to say is that when you do n/2, you do NOT have to floor or ceiling it because the extra bit that you do away with is not significant. What you are dealing with is runtime in a Big-O scenario, which does not care about the nitty bitty details. We are assuming N is HUGE, and your little extra bit of time spent trying to floor or ceiling N is never comparable.
基本上对于Big-O，您需要全面的概括，这幸运的是，您可以假设n为2的幂！
Basically for Big-O, you want sweeping generalizations, which thankfully means you can assume n is a power of 2!
这篇关于为什么我们假设对于T(n)= 2T(n/2)+ theta(1)，n是2的幂?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
