为什么这个循环需要O（2^n）时间复杂度？

有一个循环执行蛮力算法来计算5 * 3而不使用算术运算符。为什么这个循环需要O（2^n）时间复杂度？

我只需要添加五次3次，这样就需要O（3），如果输入是x * y，那么就是O（y）。但是，在一本书中，它表示需要O（2^n），其中n是输入中的位数。我不明白为什么使用O（2^n）来表示它O（y）。它是更好的方式来显示时间复杂性？你能解释我吗？

我不要求其他算法来计算这个。

int result = 0 
for(int i=0; i<3; i++){ 
    result += 5 
}

来源

2017-08-06 devDNA

运行时是一个常量（O（1）），因为此循环的运行时不依赖于任何外部参数。这真的是这本书所说的吗？你能否引用特定的措词以及它所指的是什么？ – templatetypedef

你在谈论“输入中的位数”我高度怀疑你正在舍弃一些关于本书所说的相关信息。 – bolov

在一本书中，它表示“要形成5x3，我们将从0开始并重复添加5.时间复杂度非常高，与O（2^n）一样多，其中n是输入中的位数”。但是3是0011，这是什么意思n是位数？为了表示3，它只需要2位。 O（2^2）= O（4）。为什么作者使用O（2^n），其中n是输入中的位数，而不是O（n）？ – devDNA

我认为你误读了本书的内容。

当本书谈论计算两个数的乘积的算法时，它使用乘以3 × 5的示例作为通过添加y + y +来计算x × y的更一般概念的具体实例。 .. + y，x总次数。它并没有声称具体的算法“add 5 + 5 + 5”在时间O上运行（2 ⁿ）。相反，想想这个算法：

int total = 0; 
for (int i = 0; i < x; i++) { 
    total += y; 
}

该算法的运行时间是O（x）。如果按照本书的建议测量运行时间作为数字x中的位数n的函数 - 那么运行时间为O（2 ⁿ），因为要表示您需要的数字x（log n ）位。这是polynomial time and pseudopolynomial time之间的区别，并且该书随后描述用于解决该问题的更好算法的原因在于，运行时最终成为用于表示输入而不是的位数的多项式数字的数字值为。关于小学数学乘法和加法的论述可以帮助你更好地理解这两个量之间的差异。

来源

2017-08-06 22:22:26 templatetypedef

谢谢你的回答。与本书不同，我使用数值来表示时间复杂度。嗡嗡声..我是否必须使用用于表示时间复杂度的数字位数？ – devDNA

这取决于上下文。把头脑区分开来是一个不错的主意，特别是如果你正在处理可以任意大的输入。 – templatetypedef

啊。好的。感谢您的时间和帮助。 – devDNA

不要以为用3和5想想如何计算2十亿×2十亿（大约2^31乘以2^31）

你输入的31位各（N）和您循环将执行20亿次，即2^N。

所以书是正确的。对于5x3的情况，3是2位。所以它的复杂性是O（2^2）。再次纠正。

来源

2017-08-06 22:14:55 xycf7

雅。我知道给定的运行时也是正确的，但我只是想知道为什么它使用O（2^n）来表示它O（y）。这是更好的方式来显示时间复杂性吗？ – devDNA

基本上是。这是展示复杂性的更好方法。让我详细说明一下：初始复杂性分析始于图灵机（使用磁带输入），由于状态不变，复杂性主要取决于输入的长度。和输入可以在任何碱基（基体2，基体10，基体36等），但分析在基座完成2所表示的输入端，因此复杂的数字不同的机器之间/算法可以是相当的。现代计算机也建立在二进制系统之上，几乎在任何地方使用二进制都更有意义。 – xycf7

您声称输入的时间复杂度为O（y），并且该书声称输入中的位数的时间复杂度为O（2 ⁿ）。好消息：你们都是对的！如果数字y可以用n位表示，y至多为2 ⁿ - 1

来源

2017-08-06 22:16:17 Ryan

为什么这个循环需要O（2^n）时间复杂度？

回答

相关问题