algorithm - Big-o 复杂度问题 - 线性累积幂

Question

背景

我正在尝试解决我从 2013 年斯坦福大学“算法设计与分析”类(class)中发现的一些问题。特别是问题集 1 here 中的问题 3。

概括地说:

• 您被困在一个荒岛上，您的 radio 可以以整数功率水平(即 1W、2W、3W 等)发送求救信号。
• 如果您发射足够高功率的信号，您将收到响应并获救。
• 遗憾的是，您不知道需要多少功率，n。

该问题要求您设计一个使用 Θ(n)W 总功率的算法。

作为问题集 1 中的 5 分问题，我认为这比我找到它要容易。

我的问题是

...这个算法是什么？....或者我怎样才能改变我的想法来找到一个算法？

我卡在哪里

问题指出“每次只增加 1 瓦功率”的策略将导致 Θ(n^2)W 总功率。事实上，这是真的，因为任何 n 使用的总功率是 n * (n+1) / 2。

但是，我想不出有什么策略不是:

• 大于线性；或
• 一种我通过“连续 n 不做任何事情”作弊的策略。

此外，如果我忽略 radio 的离散性一分钟并将问题分析为连续线性函数，则总功率应该可以推广到形式为 g(n) = Kn + B 的函数 g(n) (其中 K 和 B 是常数)。该线性函数表示我们需要用于控制 radio 的函数的积分。

然后，如果我取此函数的导数 dg(n)/dn，则剩下 K。如果我想要线性总功率，我应该以恒定功率驱动 radio n 次...但是如果我第一次碰巧猜对了 K，这只会导致救援.

编辑

是的，我已经想到了加倍等......但是这里的答案指出了我的想法错误。我一直试图解决“设计一个具有线性累积功耗的算法”这个问题……我认为这是不可能的。正如答案所指出的，我应该将其视为“对于给定的 n，设计一个将消耗 Kn 的算法”......即提出了什么问题。

Answer 1

我已经阅读了作业...它声明 radio 能够以整数形式传输，但这并不意味着您应该一个一个地尝试并遍历所有整数直到 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)

的要求