Big-o 复杂度问题 - 线性累积幂
Big-o complexity problem - Linear cumulative power
背景
我正在尝试解决我从 2013 年斯坦福 "Design & Analysis of Algorithms" 课程中发现的一些问题。特别是问题集 1 here.
中的问题 3
概括地说：
- 你被困在一个荒岛上，收音机可以以整数功率水平（即 1W、2W、3W 等）发送求救信号。
- 如果你发射足够强的信号，你就会收到响应并获救。
- 很遗憾，您不知道需要多少功率 n。
这道题要求你设计一个使用 Θ(n)W 总功率的算法。
作为问题集 1 中的一个 5 分问题，我想这比我找到它要容易。
我的问题是
...这个算法是什么？...或者我怎样才能改变我的想法找到一个？
我被困在哪里
问题指出策略 "just increase power by 1 watt each time" 将导致 Θ(n^2)W 总功率。事实上，这是真的，因为任何 n 使用的总功率是 n * (n+1) / 2.
但是，我想不出有什么策略不是：
- 大于线性；或
- 我通过"not doing anything for a few consecutive n's"作弊的策略。
此外，如果我暂时忽略收音机的离散性并将问题分析为连续线性函数，则总功率应该可以推广到函数 g(n) 的形式 g(n) = Kn + B （其中 K 和 B 是常量）。这个线性函数代表我们需要用来控制收音机的函数的积分。
然后，如果我对该函数求导数 dg(n)/dn，我将得到 K。即如果我想要线性总功率，我应该以恒定功率驱动收音机 n 次……但是如果我碰巧猜对了 K，这只会导致救援第一次。
编辑
是的，我已经想到了加倍等等....但是这里的答案指出了我的想法错误。我一直在尝试解决问题 "design an algorithm that has linear cumulative power consumption"...我认为这是不可能的。正如答案所指出的那样，我应该将其视为 "for a given n, design an algorithm that will consume Kn"...即问题是什么。
下面是一个简单的算法和复杂度分析：
- 最初尝试
power=1W
- 如果没有收到，请尝试
power=2*previous_power，直到收到为止
复杂度：
所以基本上我们在功率 p>= n 时停止，其中 n 是所需的阈值。
我们知道：
p>=n and p/2<n => n<=p<2n
为了达到 pW（即接收所需的水平），这意味着您之前尝试过 p/2，在此之前 p/4... 并且最初是1，所以让我们总结一下所有步骤：
1+2+4+...+p/2+p -> 2*p ~ Θ(p) = Θ(n)
我已阅读作业...
它声明无线电能够以整数形式传输，但这并不意味着您应该一个一个地尝试并遍历所有整数直到 n.
好吧，我可以给你答案，但我会试着引导你自己思考：
请注意，您需要传输等于或大于 n 的信号，所以您不可能是"going to far"。现在，有了复杂性的概念，如果你遍历所有信号，你会得到一系列 (1+2+3+...+n) 等于 Θ(n^2)，试着想出一个模式您可以跳过其中一些并获得一个总和为 Θ(n).
的系列
此任务类似于天真地搜索 Θ(n^2) 的算法，但有一些算法比这更少 - 您应该去探索它们的工作原理:)
如果你想要一个答案的方法：
您可以从 1W 开始，每一步将其加倍用于下一次传输。这样你将进行 log(n) 次尝试，每次尝试花费 i，其中 i 是该次尝试的力量。所以累积功率将是这样的： (1+2+4+8+16+...+n) 等于 2n-1 并且符合 Θ(n)
的要求
背景
我正在尝试解决我从 2013 年斯坦福 "Design & Analysis of Algorithms" 课程中发现的一些问题。特别是问题集 1 here.
中的问题 3概括地说：
- 你被困在一个荒岛上，收音机可以以整数功率水平（即 1W、2W、3W 等）发送求救信号。
- 如果你发射足够强的信号，你就会收到响应并获救。
- 很遗憾，您不知道需要多少功率 n。
这道题要求你设计一个使用 Θ(n)W 总功率的算法。
作为问题集 1 中的一个 5 分问题，我想这比我找到它要容易。
我的问题是
...这个算法是什么？...或者我怎样才能改变我的想法找到一个？
我被困在哪里
问题指出策略 "just increase power by 1 watt each time" 将导致 Θ(n^2)W 总功率。事实上，这是真的，因为任何 n 使用的总功率是 n * (n+1) / 2.
但是，我想不出有什么策略不是：
- 大于线性；或
- 我通过"not doing anything for a few consecutive n's"作弊的策略。
此外，如果我暂时忽略收音机的离散性并将问题分析为连续线性函数，则总功率应该可以推广到函数 g(n) 的形式 g(n) = Kn + B （其中 K 和 B 是常量）。这个线性函数代表我们需要用来控制收音机的函数的积分。
然后，如果我对该函数求导数 dg(n)/dn，我将得到 K。即如果我想要线性总功率，我应该以恒定功率驱动收音机 n 次……但是如果我碰巧猜对了 K，这只会导致救援第一次。
编辑
是的，我已经想到了加倍等等....但是这里的答案指出了我的想法错误。我一直在尝试解决问题 "design an algorithm that has linear cumulative power consumption"...我认为这是不可能的。正如答案所指出的那样，我应该将其视为 "for a given n, design an algorithm that will consume Kn"...即问题是什么。
下面是一个简单的算法和复杂度分析：
- 最初尝试
power=1W - 如果没有收到，请尝试
power=2*previous_power，直到收到为止
复杂度：
所以基本上我们在功率 p>= n 时停止，其中 n 是所需的阈值。
我们知道：
p>=n and p/2<n => n<=p<2n
为了达到 pW（即接收所需的水平），这意味着您之前尝试过 p/2，在此之前 p/4... 并且最初是1，所以让我们总结一下所有步骤：
1+2+4+...+p/2+p -> 2*p ~ Θ(p) = Θ(n)
我已阅读作业...
它声明无线电能够以整数形式传输，但这并不意味着您应该一个一个地尝试并遍历所有整数直到 n.
好吧，我可以给你答案，但我会试着引导你自己思考：
请注意，您需要传输等于或大于 n 的信号，所以您不可能是"going to far"。现在，有了复杂性的概念，如果你遍历所有信号，你会得到一系列 (1+2+3+...+n) 等于 Θ(n^2)，试着想出一个模式您可以跳过其中一些并获得一个总和为 Θ(n).
此任务类似于天真地搜索 Θ(n^2) 的算法，但有一些算法比这更少 - 您应该去探索它们的工作原理:)
如果你想要一个答案的方法：
您可以从 1W 开始，每一步将其加倍用于下一次传输。这样你将进行
的要求log(n)次尝试，每次尝试花费i，其中i是该次尝试的力量。所以累积功率将是这样的：(1+2+4+8+16+...+n)等于2n-1并且符合Θ(n)