【转】编程中排行前10的算法

【转】编程中排名前10的算法
AlgorithmAverage TimeWorst TimeSpace冒泡排序n^2n^21选择排序n^2n^21Counting Sortn+kn+kn+kInsertion sortn^2n^2?Quick sortn log(n)n^2?Merge sortn log(n)n log(n)depends
6. 递归 vs. 迭代

对程序员来说，递归应该是一个与生俱来的思想（a built-in thought），可以通过一个简单的例子来说明。

问题： 有n步台阶，一次只能上1步或2步，共有多少种走法。

步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。

为了走完n步台阶，只有两种方法：从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数，那么f(n) = f(n-1) + f(n-2)。

步骤2: 确保开始条件是正确的。

f(0) = 0;
f(1) = 1;

calculateProbability(50) = 0.97

组合和排列的区别在于次序是否关键。