javascript中的空间换时间算法
在我做的淘宝的在线招聘题第三题中，我使用的就是空间换时间的算法。什么是空间换时间算法？算法的复杂度包括时间复杂度和空间复杂度。很多时候，对时间复杂度的要求要远比对空间复杂度的要求高，于是就有了牺牲空间来获得时间的算法——空间换时间算法。
先看一个简单的例子，以数字排序为例，为了更好的说明问题，请先忘记javascript的sort函数:)
甲班的数学成绩出来了，按照学号排列的依次成绩是70,67,69,85,56,98,76,43,78,83,45,32,97,65,60,58,53,94,82,47,67,73。
请编写程序将甲班的成绩从大到小排序。
传统的冒泡排序方法，先遍历所有元素，找出最大的，放在第一位；然后遍历剩下的元素，找出最大的，放在第二位……重复直到结束。
冒泡排序需要计算n+(n-1)+(n-2)……+1=n(n-1)/2,所以时间复杂度为O(N2).
javascript实现（注意，为了方便比较，我将这些代码都执行了5000次排序。机器较旧的同学可能会出现假死状态）:
JavaScript:
-
<script language="javascript">
-
var result=[70,67,69,85,56,98,76,43,78,83,45,32,97,65,60,58,53,94,82,47,73];
-
var temp;
-
var time=new Date().getTime();
-
for(var m=0;m<5000;m++){
-
for(var i=result.length-1,len=result.length;i>=0;i--){
-
for(var j=len;j>=len-i;j--){
-
if(result[j-1]<result[j]){
-
temp=result[j];
-
result[j]=result[j-1];
-
result[j-1]=temp;
-
}
-
}
-
}
-
}
-
alert("执行时间:"+(new Date().getTime()-time)+"毫秒");
-
alert(result);
-
</script>
空间换时间的解法。将数组数据当成新数组索引，然后遍历新数组元素实现排序。在很多情况下，这种算法的时间复杂度可以降低到O(N)。
JavaScript:
-
<script language="javascript">
-
var result=[70,67,69,85,56,98,76,43,78,83,45,32,97,65,60,58,53,94,82,47,73];
-
var newResult=[];
-
var time=new Date().getTime();
-
for(var m=0;m<5000;m++){
-
for(var i=0,len=result.length;i<len;i++){
-
newResult[result[i]]=1;
-
}
-
for(var i=newResult.length-1,j=0;i>=0;i--){
-
if(newResult[i]){
-
result[j]=i;
-
j++;
-
}
-
}
-
}
-
alert("执行时间:"+(new Date().getTime()-time)+"毫秒");
-
alert(result);
-
</script>
这个不用多说了，利用javascript内置函数排序。
JavaScript:
-
<script language="javascript">
-
var result=[70,67,69,85,56,98,76,43,78,83,45,32,97,65,60,58,53,94,82,47,73];
-
var temp;
-
var time=new Date().getTime();
-
for(var m=0;m<5000;m++){
-
result.sort(function(a,b){return b - a});
-
}
-
alert("执行时间:"+(new Date().getTime()-time)+"毫秒");
-
alert(result);
-
</script>
由此可见，空间换时间算法在某些情况下有着很大的优势。
在测试中发现，执行上面三段代码，在ie, firefox, opera, 以及firefox 的javascript environment里结果都不一样。这是写本文之前所没考虑到的。
下面是我用时间换空间算法做的淘宝的招聘题第三题，你看看有没有更快的方法。
JavaScript:
-
<script language="javascript">
-
/*
-
请给Array本地对象增加一个原型方法，它的用途是删除数组条目中重复的条目(可能有多个)，返回值是一个仅包含被删除的重复条目的新数组。
-
*/
-
//实现部分
-
Array.prototype.m=function(){
-
var a=[],b=[];
-
for(var prop in this){
-
b[this[prop]]?a.push(this[prop]):b[this[prop]]=1;
-
}
-
return a;
-
}
-
//实例部分
-
var b=function(){
-
alert("hello,world!");
-
}
-
var a=[1,2,12,3,b,1,3,b];
-
a[10]="1111";
-
a["123"]=12;
-
a["mm"]=12;
-
alert(a.m());
-
</script>
