一些简单的时间复杂度计算

简单类型

1
2
3

x=2
while(x<n/2)
x=2*x

step-1:确定基本操作语句：x=2*x

step-2:设这一语句执行了t次，则有$2^t+1<\frac{n}{2}$，所以又$f(n)=log_2{\frac{n}{2}-1}=log_2{n}-2$

step-3:用大O表示法:$T(n)=O(f(n))=O(log_2{n})$

嵌套类型

void sort(int n,int m){
	for(int i=1;i<n;i++)
	{
		j=1;
		while(j<m)
		{
			j=j*2;
		}
	} 
}

1.while语句中的时间复杂度？

设基本操作语句$j=j*2$执行了t次，则有$2^t<m$即$f(m)=log_2{m}$，用大O表示法$T(m)=O(log_{2}{m})$。

2.整个程序的时间复杂度为多少？

外层for循环执行了n-1次，内层执行了$log_2{m}$次，则整个程序执行了$O(nlog_2{m})$

for(int i=0;i<N;i++)
{
   for(int j=i;j<N;j++)
   {
     //此处运行次数:N+N-1+N-2+...+1=1+2+3+...+N=N(N+1)/2
   }
}

当i=0，内循环执行n次；当i=1，内循环执行n-1次；….当i=n-1，内循环执行1次；所以S(n)=1+2+……n; $S(n)=\frac{n(1+n)}{2}=\frac{n^2}{2}+\frac{n}{2}$;

再加上外循环的执行次数n，$T(n)=O(\frac{n^2}{2}+\frac{n}{2}+n)$ 根据只保留最高阶项的原则，$Tn=O(n^2)$

1、考研数据结构中关于时间复杂度的计算 - 灰灰的文章 - 知乎
https://zhuanlan.zhihu.com/p/28224368

（参见文章的汉诺塔问题，里面有个错误：迭代法最后得到的应该为:$T(n)=2^{n-1}T(1)+1+…+2^n$,原文漏了$2^{n-1}$这个系数。）

2.下面的写法也可以，其中b和c皆为常量级，c前面的系数比1中写法的更简洁。