2

我最近接受了一次采访，并被要求找出提供的整数位数。我有这样的事情：

#include <iostream>

using namespace std;
int givemCountOnes (unsigned int X) {
  int count =0;
  while (X != 0 ) {
    if(X & 1)
      count++;
   X= X>>1;
  }

 return count;

}

int main() {
cout << givemCountOnes (4);
return 0;
}

我知道有更好的方法，但这不是这里的问题。

问题是，这个程序的复杂性是多少？

由于它适用于输入中的位数，人们说这是 O(n)，其中 n 是输入中的位数。

但是我觉得由于上限是sizeof(unsigned int)64 位，我应该说顺序是 o(1)。

我错了吗？

4

5 回答 5

5

复杂度为 O(N)。复杂度随所用类型的大小线性增加 ( unsigned int)。

上限无关紧要，因为它可以在将来的任何时间延长。这也无关紧要，因为总是有一个上限（内存大小，宇宙中的原子数），然后一切都可以被认为是 O(1)。

于 2013-06-13T07:59:34.953 回答
2

我只会为上述问题添加一个更好的解决方案。

在循环中使用以下步骤

x = x & (x-1);

这将一次删除最右边的 ON 位。

因此，只要有一个 ON 位，您的循环就会最大运行。当数字接近 0 时终止。

因此，复杂性从 O（int 中的位数）提高到 O（on 位数）。

于 2013-06-13T08:45:34.297 回答
0

大 O 表示法描述了最坏情况下算法步骤的计数。在这种情况下，当最后一位有 1 时。因此，当您传递 n 位数作为输入时，将有 n 次迭代/步骤。

想象一个类似的算法，它在列表中搜索 1 的计数。它的复杂度是 O(n)，其中 n 是列表长度。根据您的假设，如果您始终将固定大小的列表作为输入传递，那么算法复杂度将变为 O(1)，这是不正确的。但是，如果您在算法中固定位长：即类似的东西for (int i = 0; i < 64; ++i) ...，它将具有 O(1) 复杂度，因为它执行 64 次 O(1) 操作，您可以在这里忽略常量。否则 O(c*n) 是 O(n)，O(c) 是 O(1)，其中 c 是常数。

希望所有这些例子有所帮助。顺便说一句，对此有 O(1) 解决方案，我会在我记得时发布它:)

于 2013-06-13T08:21:20.253 回答
0

应该清除一件事：整数运算的复杂性。在这个例子中不清楚，当你工作时int，这是你机器上的自然字长，它的复杂性似乎只有 1。

但是 O-notation 是关于大量数据和大型任务的，比如说你有 n 位整数，其中 n 大约是 4096 左右。在这种情况下，复杂度加法、减法和移位至少具有 O(n) 复杂度，因此应用于此类整数的算法将是 O(n²) 复杂度（应用了 O(n) 复杂度的 n 次操作）。

不移动整数的直接计数算法（假设一位测试是 O(1)）给出 O(n log(n)) 复杂度（它涉及对 log(n) 大小的整数进行多达 n 次加法）。

但是对于固定长度的数据（即 C 的 int），大 O 分析根本没有意义，因为它基于可变长度的输入数据，也就是说，几乎任何长度到无穷大的数据。

于 2013-06-13T09:54:16.120 回答
0

O 表示法用于说明 的不同值之间的差异n。在这种情况下，n将是位数，因为（在您的情况下）位数将改变执行计算所需的（相对）时间。所以 O(n) 是正确的——一位整数需要 1 个时间单位，一个 32 位整数需要 32 个时间单位，一个 64 位整数需要 64 个时间单位。

实际上，你的算法并不依赖于数字中的实际位数，而是取决于数字中设置的最高位的数量，但那是另一回事。但是，由于我们通常将 O 称为“最坏情况”，因此它仍然是 O(n)，其中 n 是整数中的位数。

而且我真的想不出任何比 O 方面更好的方法 - 我可以想到提高循环中迭代次数的方法（例如，使用 256 个条目表，并以 8 位处理时间），但它仍然是“更大的数据 -> 更长的时间”。由于 O(n) 和 O(n/2) 或 O(n/8) 都是相同的（只是后一种情况的总时间是第一种情况的 1/8）。

于 2013-06-13T07:59:12.090 回答