时间复杂度
关于时间复杂度,最最重要的一句话就是:
将算法中基本操作的执行次数作为时间复杂度的度量
。时间复杂度并不是执行程序所需要的时间,而是执行基本操作的总次数。
考研中,常常需要比较各个时间复杂度的大小,常用的时间复杂度比较关系为:
O(1)≤O(log
2
(n))≤O(n)≤O(n
log
2
(n))≤O(n
2
)≤O(n
3
)≤...≤O(n
k
)≤O(2
n
)
*
计算时间复杂度的具体步骤如下:
-
确定算法中的基本操作以及问题的规模
-
根据基本操作执行情况计算出规模数n的函数f(n),并确定时间复杂度T(n)=O(f(n)中增长最快项/此项系数)(也就是说
只考虑最高项,且忽略最高项的系数
)
注意:有的算法中基本操作的执行次数不仅跟初始输入的数据规模有关,还和数据本身有关。比如说,一些个排序算法,同样有n个待处理的数据,但数据初始有序性不同,则基本操作的执行次数也不同。一般是依照使得基本操作执行次数最多的输入来计算时间复杂度,即最坏的情况下作为时间复杂度的度量。
例1.1
求以下算法的时间复杂度
void fun(int n)
{
int i = 1,j = 100;
while(i < n)
{
++j;
i+=2;
}
}
分析:
第一步:找出基本操作,确定规模n
-
找基本操作。多数情况下取最深层循环内的语句所描述的操作作为基本操作,显然题目中
++j;i+=2;
这两句都是基本操作。
-
确定规模n。由循环条件可以得知,循环执行的次数和n有关,故,参数n就是我们所说的规模n。
第二步:计算出n的函数f(n)
n确定之后,循环的结束与否跟i有关,i的初值为1,每次自增为2,假设i自增m次后,循环结束,则i最后的值为1+2m,因此1+2m>n,即1+2m+K=n(k为常数,弥补循环结束时i和n的差距),解的m=(n-1-K)/2,即f(n)=(n-1-K)/2,根据时间复杂度的计算原则:
只考虑最高项,且忽略最高项的系数
,所以时间复杂度
f(n)=O(n)
。
例1.2
分析以下代码的时间复杂度
void fun(int n)
{
int i,j,x=0;
for(i=0;i<n;++i)
for(j=i+1;j<n,++j)
++x;
}
分析:
++x;处于最内层循环,故,++x为基本操作,显然,n为规模,可以算出++x执行次数f(n)=n
(n-1)/2,所以时间复杂度
f(n)=O(n
2
)
例1.3
分析以下算法的时间复杂度
void fun(int n)
{
int i=0,s=0;
while(s<n)
{
++i;
s=s+i;
}
}
分析:
显而易见,规模为n,基本操作是++i,和s=s+i;i和s都是从0开始,假设执行m次之后,循环结束,则循环结束之时,s的值为m(m+1)/2。所以
由此可知时间复杂度
T(n)=O(n
1/2
)