算法导论

大学确实没有好好学这么课程，大家都是这样过来的。除了参加ACM之类比赛的同学，用心去做题，研究这些东西。一些水货，比如我。谁会去看这个。并且，根本不影响考试，考试无非就出那几道题而已。书到用时方恨少，昨天被一个同学问到：

给你一个数组array,还有一个函数rand(n)返回0-n的随机数。写一个方法，把array随机化。

我一下子不知所措，但是还是硬着头皮写了一个：

$output=array();
 $len=count($array);
 while(count($output)<$len){
  $output[rand(n)]=1;
 }
 $ret=array();
 for($output as $k=>$v){
  $ret[]=$array[$k];
 }
 $array=$ret;

然后他问我时间复杂度。

我说，这，根本就没法算啊。谁知道while那里会计算多久，如果你运气不好，一直rand出来的是一个数，那可能就是死循环了。

他说，你在想想。

我说，算了。想不出来。

他说有个不算好的算法，O(N)时间复杂度。

for($i=0,len=count($array);$i<$len;$i++){
  $temp=$array[i];
  $j=rand(n);
  $array[i]=$array[$j];
  $array[j]=$temp;
 }

我觉得太丢人了。没想到那货说了一句，这是算法导论第五章第三节的内容。

擦。有一种强烈地被鄙视的感觉。

虽然说考脑筋急转弯，纸上写代码什么的，可能google都说没用。但是这些基本的知识，还是要会的吧。如果我们只会ghost一个系统，那tmd还好意思跟人家说你学了四年计算机？

所以，在学校的同学，一定要抽时间，好好看几遍，《算法导论》，然后把所有的题目都做了。

这将大有裨益。

另外，这道题,你知道更快的算法吗？