我正试图解决我从2013年斯坦福大学 "Design & Analysis of Algorithms "课程中发现的一些问题。尤其是问题集1中的问题3 此处.
总的来说，它说。
这个问题要求你设计一个总功率为Θ（n）W的算法。
作为问题集1的5分题，我推测这比我发现的要简单。
....这个算法是什么？.......或者说，我怎么才能改变思路找到一个？
问题中指出，"每次增加1瓦功率即可 "的策略会导致总功率为Θ(n^2)W。事实上，这是真的，因为任何一个人使用的总功率都是 n 是 n * (n+1) / 2.
然而，我想不出任何策略是不。
另外，如果我暂时不考虑无线电的离散性，而把这个问题作为一个连续的线性函数来分析，那么总功率应该可以概括为函数 g(n) 属于 g(n) = Kn + B 其中K和B为常数）。这个线性函数将代表我们需要用来控制无线电的函数的积分。
然后，如果我取这个函数的导数，dg(n)dn，我就剩下K了，也就是说，如果我想获得线性的总功率，我应该以一个恒定的功率来驱动收音机。n 次......但这只有在我碰巧第一次猜对了K的情况下才会有救。
是的，我已经想到了加倍等......但这里的答案指出了我思维的错误。我一直想解决 "设计一个线性累积功耗的算法 "这个问题......我认为这是不可能的。正如答案所指出的那样，我应该把它想成 "对于给定的? n，设计一个能消耗Kn的算法"......即问题提出的内容。
我看了一下作业......上面说无线电是可以用整数来传输的，但是并不是说你要一个一个的去试，把所有的整数都试一遍，直至 n.
好吧，我可以给你答案，但我只想引导你自己去思考。
请注意，你需要传输一个相等的信号。或以上 比 n所以你不可能 "走得太远"。现在，用复杂度的概念，如果你把所有的信号都看一遍，你会得到一系列的(1+2+3+......+n)，相当于 Θ(n^2)试着想一个模式，你可以跳过其中的一些，并得到一个系列，结果是和 Θ(n).
这个任务类似于搜索算法，它天真地去寻找 Θ(n^2)但也有一些算法被简化到比这更小的程度--你应该去探索它们是如何工作的 :)
如果你想要一个答案的方法。
你可以从1W开始，每走一步，下一步就把它翻倍。这样，你将做
log(n)次，而每次尝试的成本是i其中i是该尝试的力量。所以累计的力量会是这样的。(1+2+4+8+16+...+n)等于...2n-1并符合以下要求Θ(n)
这里有一个简单的算法和复杂性分析。
power=1Wpower=2*previous_power 直到收到复杂性。
基本上我们停止时的权力 p>= n，其中n为期望阈值.我们知道。
p>=n and p/2<n => n<=p<2n
为了达到 pW (即为了接收所需的级别)这意味着你之前尝试过p2，之前是p4......最初是1，所以让我们总结一下所有的步骤。
1+2+4+...+p/2+p -> 2*p ~ Θ(p) = Θ(n)