首页 > 代码库 > 用MATLAB比较算法的优劣

用MATLAB比较算法的优劣

《算法导论》第一章《算法在计算中的作用》有一道题目,如下:

1.2-2:假设我们正比较插入排序与归并排序在相同机器上实现。对规模为n的输入,插入排序

运行8n^2步,而归并排序运行64nlgn步。问对哪些n值,插入排序优于归并排序。

解法为:

列方程:8*n^2<=64nlgn

化简: n<=8*lgn    =>  n<=lg(n^8)  =>  10^n<=n^8   => n^8-10^n=>0

可以用matlab画出n^8-10^n=>0的图形


由图形可以判断函数的零点在[-4,4]之间,接下来求解零点。

程序: f=inline(‘n^8-10^n‘);x1=fzero(f,-4),x2=fzero(f,4)

结果:x1 =

 

  -0.795384222885413

 

 

x2 =

 

   1.572313792150843

舍去负值,得到正解x=1.572313792150843

再将x取整,即x=1,n=1,n值小于等于1时,8*n^2的插入排序比64nlgn的归并排序优良。

总结:本文用matlab对两个算法进行了性能上的比较,提出一种比较算法性能的普世方法。

在学习算法过程中必然会涉及到计算算法复杂度,和对算法的性能分析,而matlab作为一个强大的

数学工具箱,不失为学习算法的一个好工具。

用MATLAB比较算法的优劣