算法效率是指算法执行的时间,算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法:
1)事后统计的方法
2)事前分析估算的方法
现在考虑线性查找。线性查找算法顺序比较数组中的元素与键值,直到找到键值或者数组已搜索完毕。如果该键值没有在数组中,那么对于一个大小为n的数组需要n次比较。如果该键值在数组中,那么平均需要n/2次比较。该算法的执行时间与数组的大小成正比。如果将数组大小加倍,那么,比较次数也会加倍。该算法是呈线性增长的,增长率是n的数量级。计算机科学家使用大O符号表示数量级。使用该符号,线性查找算法的复杂度就是O(n),读为“n阶”。
例如,考虑下面循环的时间复杂度:
for(i = 1; i <= n; i++) { k = k + 5; }
这是一个常量时间c,对于执行
k = k + 5;
因为循环了n次,因此其时间复杂度是
T(n) = (a constanc c) * n = O(n)
1)分析二分查找算法
是在一个有序数组中查找一个键值。
2)分析选择排序算法
是在线性表中找到最小数,并将其放在表头,然后在剩下的数中找到最小数,放到第一个数之后,这样一直做下去,直到线性表中仅剩一个数为止。
3)分析插入排序算法
是在已排好序的子数组中反复插入一个新元素,直到整个数组全部排好序。
4)分析汉诺塔问题
按如下方式借助塔C将n个盘子从塔A递归地移动到塔B:
1)借助塔B将前n-1个盘子从塔A移动到塔C
2)将盘子n从塔A移动到塔B
3)借助塔A将n-1个盘子从塔C移动到塔B
例如,一个找出裴波那契数的递归方法
/** The method for finding the Fibonacci number */ public static long fib(long index) { if (index == 0) // Base case return 0; else if (index == 1) // Base case return 1; else // Reduction and recursive calls return fib(index - 1) + fid(index - 2); }