通常我们需要一种方法来对不同的算法来进行比较,一般来说,解决同样的问题有多种算法,那么在不同的客观条件下如何对不同的算法进行取舍呢?
一,算法的目标:
1,容易理解,编码和调试
优秀的算法通常是简洁而清晰的,这样带来的直接好处就是易于编码和理解,同时这样算法也必定是健壮的,如果一个算法晦涩难懂,则很可能其中会隐藏较多的错误。
2,最小的代价
算法的代价的最小化是指其执行时间最短且占用的存储空间最少,它们之间 往往是相互矛盾的,然而一般而言,算法的执行时间是主要的评价标准。
二,算法的执行时间
算法的执行时间等于它所有基本操作执行时间之和, 而一条基本操作的执行时间等于它执行的次数和每一次执行的时间的积,
如下:
算法的执行时间 = 操作1 + 操作2 + ... + 操作n
操作的执行时间 = 操作执行次数 X 执行一次的时间
然而存在一个问题,不同的编程语言,不同的编译器,或不同的CPU等因素将导致执行一次操作的时间各不相同,这样的结果会使算法的比较产生歧义, 于是我们假定所有计算机执行相同的一次基本操作所需时间相同,而把算法中基本操作所执行的最大次数作为量度。就是说我们把算法的执行时间简单地用基本操作的执行次数来代替了。
那么除此之外,基本操作是什么? 它可以是基本运算,賦值,比较,交换等,如在排序中,基本操作指的是元素的比较及交换。而在线性查找中,它是数据的比较。
三,时间复杂度和大O表示法
当问题规模即要处理的数据增长时, 基本操作要重复执行的次数必定也会增长, 那么我们关心地是这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。这个所谓的数量级就称为算法的渐近时间复杂度(asymptotic time complexity), 简称为时间复杂度。如何分析这个数量级呢? 由于基本操作的执行次数是问题规模n 的一个函数T(n), 所以问题就是我们要确定这个函数T(n)是什么, 然后分析它的数量级, 拥有相同数量级的函数 f(n) 的集合表示为 O(f(n)), O是数量级的标记。如果T(n)的数量级和f(n)相同,
显然T(n) ∈ Of(n)。这个函数的值表示当我要处理的数据量增长时,基本操作执行次数以什么样的比例增长。即n增长时,T(n)增长多少?
四,几个例子
比如说一个冒泡排序的算法, 假如有10个数,第一次循环比较9次,第二次循环比较8次,以此类推,一共
循环9次,那么总次数为 9+8+7+6+5+4+3+2+1 等于45次,则对于N个数来说, 总比较次数为 N(N-1)/2 次,
可见得对于N个数来说, 它的比较次数的数量级已达到N的平方, 即 T = N(N-1)/2 ,则我们说它的比较操作的
时间复杂度为 O(n2) (n的平方)。
另外对于一个数组的线性查找呢? 很显然, 在最坏的情况下,10个数要比较10次,那么对于N个数来说,
要比较N次, 平均 N/2 次, 即 T = N/2 , 它的数量级是一次的,则我们说这个线性查找的时间复杂度是线性的,
即 O(n).