数据结构基础篇(3)--算法时间复杂度的常用算法

一、常数阶

int sum =0,n=100; /*执行一次*/ sum=(1+n)*n/2; /*执行一次*/ System.out.print(sum); /*执行一次*/

由于T(n)=O(f(n)),此时f(n)=3,根据之前推导大O阶的方法，第一步就是把常数3改为1，没有最高想，所以它的时间复杂度为O(1)。、

二、线性阶

int i,n=100; for(i=0;i<n;i++){ //时间复杂度为O(1)的程序 }

它的循环的时间复杂度为O(n)。

三、对数阶

int count=1； while(count<n){ count = count*2; }

由于每次count乘以2之后，和n就更接近，意思就是说，有多少个2相乘后大于n，则会退出循环。 由2^x=n 得到x=log2(n),即以2为底的n，时间复杂度记为O(logn).

四、平方阶

int i,n=100; for(i=0;i<n;i++){ for(int j=i;j<n;j++){ //时间复杂度为O(1)的程序 } }

当i=0时，内循环执行了n次，当i=1时，执行了n-1次……当i=n-1时，执行了一次 n+(n-1)+(n-2)+…+1=n(n+1)/2 用我们推导大O阶的方法，最终保留了最高项，所以它的时间复杂度为O(n^2)。

五、常见的时间复杂度表

执行次数函数阶12O(1)2n+3O(n)3n^2+2n+1O(n^2)5log2(n)+20O(logn)2n+3nlog2(n)+19O(nlogn)6n^3+2n^2+3n+4O(n^3)2^nO(2^n)

文章只是作为自己的学习笔记，借鉴了网上的许多案例，如果觉得阔以的话，希望多交流，在此谢过…