问题描述
最近,我对算法感兴趣,并且一直在观看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的幂?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!