xinbiancheng.cn

如何计算时间复杂度

目录

1、分析1+2+......+100时两种时间复杂度

package xinbiancheng.cn;
public class algorithm1 {
	public static void main(String[] args) {
		// java算法1
		int sum = 0;
		int end = 0;
		for(int i=1;i<=end;i++) {
			sum+=i;
		}
		// java 算法2 
		sum=(1+end)*end/2;
	}
}

算法一的时间频度T(n) = n+1

算法二的时间频度T(n)=1

根据时间频度可以推算时间复杂度

时间复杂度计算原则

1、忽略常量项

例如：

2n+20 和 2n 随着n变大，执行曲线无限接近，20可以忽略

3n+10 和 3n 随着n变大，执行曲线无限接近，10可以忽略

2、忽略低次项

例如：

2n^2+3n+10 和 2n^2 随着n变大，执行曲线无限接近，可以忽略3n+10

n^2+5n+20 和 n^2 随着n变大，执行曲线无限接近，可以忽略5n+20

3、忽略系数

例如：

随着n值变大，5n^2+7n和 3n^2+2n,执行曲线重合，说明这种情况下，5和3可以忽略

计算时间频度

用常数1代替运行时间中的所有加法常数T(n) = 3n^2+7n+6 => T(n)=3n^2+7n+1

忽略低次项 T(n) = 3n^2+7n+1 = T(n) =3n^2

忽略系数  T(n) = 3n^2  => T(n) = n^2 =>O(n^2)

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2^n)＜Ο(n!)<O(n^n)

常见时间复杂度java代码如下：

常数阶O(1)

无论代码执行了多少行，只要没有循环等复杂结构，可以认为时间的复杂度就是O(1)

int i=1;
int j=100;
i++;
++j;

对数阶O(log2n)

如果N = ax (a>0 且 a<>1),那么数x叫做以a为底N的对数，记作x=logan

a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”

int i=1;
int n=100;
while(i<n) {
	i=i*2;
}

线性阶O(n)

for循环里面的代码会执行n遍

int n=100,sum=0;
for(int i=1;i<=n;i++) {
	sum=sum+i;
}

线性对数阶O(nlogn)

将时间复杂度为O(logn)的代码循环N遍的，那么它的时间复杂度就是n*O(logN)

int n=100,sum=0;
for(int i=1;i<=n;i++) {
	for(int j=1;j<=n;j++) {
		j=j*2;
		sum=sum+i;
	}
}

平方阶O(n2)

如果2层循环就是平方阶

int n=100,sum=0;
for(int i=1;i<=n;i++) {
	for(int j=1;j<=n;j++) {
		sum=sum+i;
	}
}

K次方阶O(nk)

O(n3)相当于三层n循环，O(nk)相当于k层n循环