算法时间复杂度分析和空间复杂度分析

算法时间复杂度分析

一、分析方法

1、事后分析估算方法

public static void main(String[] args){
long start = System.currentTimeMillis();
int sum = 0;
for(int i = 0;i<100;i++){
sum += i;
}
long end = System.currentTimeMillis();
System.out.println(end – start);
}

缺点：测试完后发现测试的算法很糟糕，那么需要更换算法，之前的努力就白费了。

2、事前分析估算方法

        概念：在计算机程序编写前，依据统计方法对算法进行估算。

高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：

        最终在分析程序的运行时间时，最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间，最重要的就是把核心操作的次数和输入规模 n 关联起来。（忽略条件循环）

总结：

二、算法时间复杂度的表示方法

1、大O记法

        在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数。记作：T(n)=O(f(n)); 

规则：

示例：

// 三次 -> O(1)
int sum = 0;//执行一次
int n = 100;//执行一次
sum = ( n + 1 ) * n / 2;//执行一次

// n+2次 -> O(n)
int sum2 =0;//执行一次
int n2 = 0;//执行一次
for (int i = 1; i<= n ;i++){
sum2 += i;//执行 n 次
}

// n^2+2次 -> O(n^2)
int sum3 =0;//执行一次
int n3 = 0;//执行一次
for (int i = 1; i <= n;i++){
for (int j = 1; j <= n;j++){
sum += i;//执行 n^2 次
}
}

2、常见的大O阶

复杂度从低到高如下：

三、函数调用的时间复杂度分析

例如：

public class lession1 {
public static void main(String[] args){

// 2n^2+n -> O(n^3)
int n = 100;
show(n); //执行n次
for (int i = 0;i<n;i++){ //执行n^2次
show(i);
}
for (int i = 0;i<n;i++){ //执行n^2次
for (int j = 0;j<n;j++){
System.out.println(j);
}
}

}
public static void show(int i){ //执行n次
for (int j = 0;j<i;j++){
System.out.println(i);
}
}
}

最坏情况：

public int search(int num){
int[] a = {1,2,3,5,6,8,4,5};
for (int i = 0; i < a.length; i++) {
if(num == a[i]){
return i;
}
}
return num;
}

最好情况：
查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)

最坏情况：
查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为0(n)

算法空间复杂度分析

一、基本数据类型内存占用

1、情况如下表：

        2、一个引用需要八个字节：.一般内存的使用，如果不够8个字节，都会被自动填充为8字节。

public class Student{
public int a = 1;//整形成员变量占4个字节
//对象本身占16字节。
//16+4 = 20，自动补为24（8位单位）
}

        3、java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节 = 24个字节)再加上保存值所需的内存。

二、算法空间复杂度的表示方法

例如：

// 4+4 -> O(1)
public int[] reverse1(int[] arr){
int n = arr.length;//申请四个字节
int temp;//申请四个字节
for (int start = 0,end = n-1; start <= end ; start++,end–) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
return arr;
}
// 4+n*4+24 ->O(n)
public int[] reverse2(int[] arr){
int n = arr.length;//申请四个字节
int[] temp = new int[n];//申请n*4个字节 + 数组自身头信息开销的24字节
for (int i = n-1; i >= 0 ; i–) {
temp[n-1-i] = arr[i];
}
return arr;
}