数据结构(一)时间复杂度分析

简单的时间复杂度分析

算法时间复杂度:O(1),O(n),O(lgn),O(nlogn),O(n^2)
大O描述的是算法的运行时间和输入数据之间的关系

看一个对输入数据进行求和的算法:
1 public static int sum(int[] nums) {
2 int sum = 0;
3 for(int num: nums) sum += num;
4 return sum;
5 }

第3行,对于nums中的每个数,都要进行这种操作,执行时间我们计为常量c1;第2行和第4行的执行时间计做常量c2;
得出该算法的运行时间与输入数据(数组个数规模)之间是一种线性关系:
T = c1*n + c2

分析时间复杂度时,忽略常数。线性关系的时间复杂度为O(n),因此该算法的时间复杂度为O(n)。
再看下面的关系:
T1 = 2*n + 2 O(n)
T2 = 2000*n + 10000 O(n)
T3 = 1*n*n + 0 O(n^2)

当n等于10时,T2=12000,T3=100,T2时间明显超过T3,而O(n^2)的时间复杂度是高于O(n)的,不是违背了?
其实,大O的表示,指的是渐进时间复杂度,描述的是n趋近于无穷时的情况。
所以,在n趋于无穷时,高阶算法时间复杂度O(n^2) > 低阶算法时间复杂度O(n)是正确的。
在实际中,对于n比较小的时候,有可能一个高阶算法的常数比较小,反而运行时间会快于低阶算法的。最典型的例子,比如高级的快速排序算法或归并算法,对于较小的数组转而使用插入排序这种方式来进行优化。利用的就是插入排序算法的常数比快速排序算法或归并排序算法的常数要小的原理;
当n趋于无穷的情况下,同时存在高阶和低阶时,低阶是可以被忽略的,请看下面的时间复杂度:
T1 = 300n + 10 O(n)
T2 = 1*n*n + 300n + 10 O(n^2)

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理