时间复杂度和整数输入 [英] Time complexity and integer inputs

问题描述

我遇到了一个问题，要求描述以下代码在Big O中的计算复杂度:

I came across a question asking to describe the computational complexity in Big O of the following code:

i = 1;
while(i < N) {
    i = i * 2;
}

我发现了这个堆栈溢出问题，要求答案，投票得最多的答案是Log2(N).

I found this Stack Overflow question asking for the answer, with the most voted answer saying it is Log2(N).

乍一看答案似乎是正确的，但是我记得学习过伪多项式运行时，以及计算复杂性如何衡量相对于输入长度而非值的难度.

On first thought that answer looks correct, however I remember learning about psuedo polynomial runtimes, and how computational complexity measures difficulty with respect to the length of the input, rather than the value.

因此对于整数输入，复杂度应根据输入中的位数进行.

So for integer inputs, the complexity should be in terms of the number of bits in the input.

因此，该函数不应该是O(N)吗?因为循环的每次迭代都会将i中的位数增加1，直到达到与N相同的位数为止.

Therefore, shouldn't this function be O(N)? Because every iteration of the loop increases the number of bits in i by 1, until it reaches around the same bits as N.

推荐答案

这取决于一个重要的问题:乘法常数运算是吗?"

It depends on important question: "Is multiplication constant operation"?

在现实世界中，通常将其视为常量，因为您具有固定的32或64位数字，并且将它们相乘总是需要相同(=恒定)的时间. 另一方面，您有一个限制，即N <32/64位(或其他任何使用的位).

In real world it is usually considered as constant, because you have fixed 32 or 64 bit numbers and multiplicating them takes always same (=constant) time. On the other hand - you have limitation that N < 32/64 bit (or any other if you use it).

从理论上讲，您不将乘法视为常数运算，或者对于某些特殊的算法，其中N可能增长得太多而无法忽略乘法复杂性，那么您是对的，您必须开始考虑乘法的复杂性.

In theory where you do not consider multiplying as constant operation or for some special algorithms where N can grow too much to ignore the multiplying complexity, you are right, you have to start thinking about complexity of multiplying.

乘以常数(在这种情况下为2)的复杂性-您每次必须遍历每个位，并且有log_2(N)个位.

The complexity of multiplying by constant number (in this case 2) - you have to go through each bit each time and you have log_2(N) bits.

在达到N

其复杂度为log_2(N) * log_2(N) = O(log_2^2(N))

PS:Akash的优点是可以将乘以2表示为常数运算，因为您在二进制文件中唯一需要做的就是加零"(类似于人类可读"格式的乘以10)，您只需添加零4333 * 10 = 43330)

PS: Akash has good point that multiply by 2 can be written as constant operation, because the only thing you need in binary is to "add zero" (similar to multiply by 10 in "human readable" format, you just add zero 4333*10 = 43330)

但是，如果乘法不是那么简单(您必须遍历所有位)，那么前面的答案是正确的

However if multiplying is not that simple (you have to go through all bits), the previous answer is correct

这篇关于时间复杂度和整数输入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！