优化算法复杂度的技巧

优化算法复杂度的技巧－位操作

On September 29, 2010, in 算法, 笔试面试, by sponge

算法是很巧妙的东西，很多时候你以为你写了一个时间复杂度和空间复杂度最低的算法，但实际上还有更好的方法，让我们来看两个通过位操作优化的小算法。

第一个题目相对比较简单，第二个题目我觉得大多数人也能给出比较好的答案，大家不妨先思考下再看下面的答案。

第一题：这个题很多人应该不会陌生，有同学会说我们可以通过简单的"+"运算就能达到目的：

a = a + b;
b = a - b;
a = a - b;

通过上面的式子，我们可以达到交换两个数的目的。但是，这样是不是就足够了呢？我们需要考虑个问题，如果a和b相加后溢出了怎么办？
谢@tanghao指正，这里溢出也不会有什么问题

因为可能会出现溢出，所以我们就不能使用上面的方法。这时，我们可能就会想到位操作，想到异或(xor)操作，让我们试试可不可以用xor来实现交换：

a = a ^ b;
b = a ^ b;
a = a ^ b;

我们知道，两个相等的数异或后的结果是0，而0异或任何数都等于那个数本身。所以我们发现，通过上面的式子，我们完全可以将两个数交换而不存在溢出的问题。

第二题：下面我们来看第二题。

按照正常的思路，我们会得到如下的算法：

让我们来看下这个算法的复杂度，开始排序的时间复杂度是O(nlogn)，后来扫描数组的时间复杂度是O(n)，空间复杂度为O(1)。

问题解决了，但是，是否还有时间复杂度更低的方法呢？通过上一题的提示，我们又可以想到xor操作，不要忘记，两个相等的数异或后为0，而0异或任何数都等于原数；并且，异或满足交换律，即a^b^c = c^b^a。因此，我们可以尝试下面的方法：

int i;
int temp = 0;
for(i = 0; i&lt;2n+1; i++){
        temp = temp ^ a[i] ; //数组a为给定数组
}
printf("%d", temp);

因为数组a中，有n个数是成对出现的，因此这2n个数异或完后结果是0，0再异或剩下一个数，结果就是我们要求那个不配对儿的数。所以，我们只需要对数组扫描一遍，在O(n)的时间复杂度，O(1)的空间复杂度内便可以完成题目的要求。

anyShare分享到：