两个数组比较（算法） 怎样算最优化！

Question

不论怎样算，总之是要遍历两个数组要比较
a1.length * a2.length次
</慕白兄>

Answer 1

cpp2017(慕白兄) ：这样做的时间复杂度为O(2)。其实可以优化一下：1 为每个对象定义哈希算法，
2 把每个数组按哈希值排序，
3 从头到尾比较数组的元素排序时间复杂度为O(1.3)，之后的遍历过程时间复杂度就降到O(1)了。

Answer 2

我说说我的一点浅见：
考虑到是在JavaScript中实现，先利用String.sort()对两个数组排序，再将数组的最小值与数组的最小值比较……排除比它小的再比权。基本思路就是这样了……

Answer 3

简单数据类型这样就够了，对于对象类型要考虑到对象的toString方法能否为不同的对象返回不同值，因为sort方法在不指定比较函数是默认使用toString方法来比较的。考虑下面的例子：
function myObj(n){
this.emu=n;
}
var myAr=[new myObj(5),new myObj(3),new myObj(3),new myObj(7),new myObj(2),new myObj(6)];
myAr.sort();
for (var i=0;i<myAr.length;i++)
document.write(myAr[i].emu+"<Br>");当然这个例子中改一下比较函数就成了：
myAr.sort(function (a,b){return a.emu-b.emu});但是更复杂的情形下就未必了，比尔有多个属性和方法的对象，怎么compare？

Answer 4

回复人： cpp2017(慕白兄) ( ) 信誉：100  2003-05-19 18:05:00  得分:0 
 
 
  不论怎样算，总之是要遍历两个数组要比较
a1.length * a2.length次
</慕白兄>双手同意，但我想时间复杂度肯定不是O(2)，只见过0(1)的，从没见过o（2）的，以比较为基本操作的时间复杂度为o(a1.length * a2.length)。

Answer 5

我说一个方法：·利用二叉树排序算法，需要修改一下，添加一个条件如果想等就存起来，否则创建二叉树
最终你将得到一个排序好的树组，这个数组将是存在差异的所有元素，而之前保存起来的就是你要的相同元素，一举两得。这种算法的时间复杂度为O(a1.length + a2.length),但是基本操作为想二叉树中添加节点的操作。

Answer 6

llrock(百乐宝||昨夜星辰):
----------------------------------------------------------
以比较为基本操作的时间复杂度为o(a1.length * a2.length)。
----------------------------------------------------------那要是a1.length=100,a2.length=100,时间复杂度就是O(10000)咯！？至于排序或者构建二叉树，没有compare算法怎么排怎么构？