Tag: 复杂性 理论

这种乘法算法的时间复杂度是多少？

对于经典的访谈问题“如何在没有乘法运算符的情况下执行整数乘法？”，最简单的答案当然是C中的以下线性时间算法： int mult(int multiplicand, int multiplier) { for (int i = 1; i < multiplier; i++) { multiplicand += multiplicand; } return multiplicand; } 当然，有一个更快的算法。 如果我们利用向左移位的属性相当于将2乘以移位的位数的幂，我们可以向上移位到最接近的2的幂，并使用我们之前的算法加起来从那里。 所以，我们的代码现在看起来像这样： #include int log2( double n ) { return log(n) / log(2); } int mult(int multiplicand, int multiplier) { int nearest_power = 2 ^ (floor(log2(multiplier))); multiplicand << nearest_power; for […]

找出数组中的重复元素

存在大小为n的数组，并且数组中包含的元素在1和n-1之间，使得每个元素出现一次并且仅一个元素出现多于一次。 我们需要找到这个元素。 虽然这是一个非常常见的问题，但我仍然没有找到合适的答案。 大多数建议是我应该将数组中的所有元素相加，然后从中减去所有索引的总和，但如果元素的数量非常大，这将不起作用。 它会溢出。 关于使用异或门dup = dup ^ arr[i] ^ i ，也有一些建议，我不清楚。 我已经提出了这个算法，这是一个增加算法的增强，并将在很大程度上减少溢出的机会！ for i=0 to n-1 begin : diff = A[i] – i; sum = sum + diff; end diff包含duplicate元素，但是使用这个方法我无法找到重复元素的索引。 为此，我需要再次遍历数组，这是不可取的。 任何人都可以提出一个更好的解决方案，不涉及添加方法或XOR方法在O（n）中工作？