说到分析算法，我们通常应该考虑的是算法的计算时间。我们可以根据运行时间选出一个或者几个可行的算法。 在能够分析一个算法之前，我们必须有一个要使用的实现技术的模型，我们假定一种通用的单处理器计算模型------随机访问机（RAM）来作为我们的实现技术，算法可以用计算机程序实现，在RAM模型中，指令一条接着一条地执行，每条指令所需时间为常量。（算术指令，数据移动指令和控制指令）。 一般来说，算法需要的时间与输入的规模同步增长，所以把一个程序的运行时间描述成其输入规模的函数，为此，我们要更仔细的定义输入规模和运行时间。 输入规模根据研究的问题来度量，如排序，则是输入的项数；如俩数相乘，输入规模的最佳量度是用通常的二进制记号表示输入所需的总位数。而输入一个图，输入规模可以用图中顶点数和边数来描述。 一个算法在特定输入上的运行时间是指执行的基本操作数或者步数。我们定义执行每行伪代码需要常量时间，这样我们可以通过再算出每行运行的次数来大致知道运行时间。我们知道一个插入排序的最佳情况的运行时间是公式：an b(n为未知数)，而最坏情况是an2 bn c，而平均情况往往和最坏情况一样差，为什么这样说？插入排序的最好情况是直接插入到正确位置，我们可以说仅仅运行一次，然而最坏情况是进行n次，平均情况是进行n/2次，平均情况和最坏情况中，n的次数相同，也是二次函数。 增长量级，我们有时候对增长率很感兴趣，而我们只考虑最重要的项，那就是最大次数的项。 如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级，那么我们通常认为前者比后者更有效。 分治法： 分解，解决，合并。 归并排序是把已经排好序的两组合并在一起，分治算法很简单，分开解决然后合并，我以python来简单介绍。 这里归并之前，我们可以采用冒泡排序，何为冒泡排序？比如我们有数字3 5 6 4 2，我们希望把它从小到大排列，我们可以这样，让第一个数字和第二个数字比较，如果list[0] |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
