求解时间复杂度和空间复杂度

绝地灬酷狼 2022-11-04 15:29 225阅读 0赞

### 时间复杂度 ###

*  算法效率
 *  时间复杂度
 *   *  评估算法运行时间
     *  大O渐进表示法
     *  最好/最坏/平均时间复杂度
     *  实例：
     *  计算耗时
     *  时间复杂度的比较
 *  空间复杂度
 *   *  实例

# 算法效率 #

算法效率分为两种：第一种是时间效率，第二种是空间效率。  
时间效率被称为时间复杂度，空间效率被称为空间复杂度

时间复杂度：主要衡量一个算法的运行速度。  
空间复杂度：主要衡量一个算法所需要的额外空间

# 时间复杂度 #

时间复杂度：主要衡量一个算法的运行速度。  
我们不会直接使用算法的运行时间去衡量，因为无法选定一个不变的客观运行环境，例如：在不同的机器上运行相同的算法，时间可能也会不相同。  
我们发现一个算法所花费的时间与语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。

## 评估算法运行时间 ##

1、和数据规模有关  
2、计算该算法的指令个数  
3、在考虑原始数据的情况下

## 大O渐进表示法 ##

在实际计算时间复杂度的时候，我们并不一定需要计算精确的执行次数，只需要大概执行次数，在这里我们使用大O渐进法.

大O符号是用于描述函数渐进行为的数学符号。  
推到大O阶：  
1、用常数1，取代运行时间中所有加法常数。  
2、在修改的运行次数函数中，只保留最高阶项  
3、如果最高阶存在且不是1，则去除这个项的系数，得到的结果就是大O阶。  
（即：保留最高项，最高项系数化为1）

## 最好/最坏/平均时间复杂度 ##

算法的时间复杂度存在最好/最坏/平均的情况：

最坏情况：任意输入规模的最大运行次数（上界）  
平均情况：任意输入规模的期望运行次数  
最好情况：任意输入规模的最小运行次数（下界）

在实际情况中，我们一般考虑的是算法的最坏运行情况 即：最坏时间复杂度

## 实例： ##

void fun(int N){ 
    	int count = 0;
    	for(int i = 0; i < N; i++){ 
    		count++;
    	}
    	int M = 10;
    	while(M--){ 
    		count++;
    	}
    }

本题的时间复杂度，count++是出现次数最多的，f(n)=N+10 。使用大O渐进法表示，那么该算法的时间复杂度为O(N).

void fun(int N){ 
    	int count = 0;
    	for(int i = 0; i < N; i++){ 
    		for(int j = 0; j < N; j++){ 
    			count++;
    		}
    	}
    	int M = 10;
    	while(M--){ 
    		count++;
    	}
    }

本题的时间复杂度，count++是出现次数最多的，f(n)=N2\+10 。使用大O渐进法表示，那么该算法的时间复杂度为O(N2).

void fun(int N){ 
    	int count = 0;
    	for(int i = 0; i < 100; i++){ 
    		count++;
    	}
    }

本题的时间复杂度，count++是出现次数最多的，f(n)=100 。使用大O渐进法表示，那么该算法的时间复杂度为O(1).

4：冒泡排序

void bubbleSort(int[] array) { 
    	for (int end = array.length; end > 0; end--) { 
    		boolean sorted = true;
    		for (int i = 1; i < end; i++) { 
    			if (array[i - 1] > array[i]) { 
    				Swap(array, i - 1, i);
    				sorted = false;
    			}
    		}
    		if (sorted == true) { 
    			break;
    		}
    	}
    }

本题的时间复杂度：我们可以将数组长度array.length看做N，最外层循环为N次，内层循环为从 end == N，一直到 end ==1；循环一共执行了：  
end = n --> 1…(n-1)  
end =n-1 --> 1…(n-2)  
…  
end = 1 --> 0  
这是一个等差数列求和，n(0+n-1)/2 即：（n2\-n）/ 2  
所以时间复杂度为 O(n2)

5：二分查找

int binarySearch(int[] array, int value) { 
    	int begin = 0;
    	int end = array.length - 1;
    	while (begin <= end) { 
    		int mid = begin + ((end-begin) / 2);
    		if (array[mid] < value)
    			begin = mid + 1;
    		else if (array[mid] > value)
    			end = mid - 1;
    		else
    		return mid;
    	}
    	return -1;
    }

本题：数据规模是N=array.length 我们也只需计算循环的次数，  
假设10个数  
10 ——5————2—————1  
1次循环 1次循环 1次循环  
即 2x-1=n  
x=log(n)+1 即 ： 大O表示为：O(log(N))

6：阶乘递归

long factorial(int N) { 
    	return N < 2 ? N : factorial(N-1) * N;
    }

本题：我们可以根据递归进行的次数计算：  
假设4个数（即 N=4），那么需要递归3次，同理 N 需要递归 N-1次，  
所以时间复杂度为O(n)

7：斐波那契

int fibonacci(int N) { 
    	return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

本题为双路递归，可以理解为想象为一个二叉树，  
我们可以想象每一个结点都是需要递归到的，计算所有结点的个数，就是要需要的次数。  
为了简单，我们可以想象成满二叉树（不影响结果）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]  
所有节点的个数，即等比数列求和：  
为 2^n - 1  
大O表示为 O(2n)

## 计算耗时 ##

1.假如有一个算法的时间复杂度是 O(n2)，并且已知该算法处理 1000 个数据需要耗时 7 秒中。请问，处理 6000 个数据需要耗时多少秒？  
分析：数据规模扩大了，6倍 时间复杂度为O(n2)，  
所以 62\*7 = 252s

2.假如有一个算法的时间复杂度是 O(n)，并且已知该算法处理 1000 个数据需要耗时 7 秒中。请问，处理 6000 个数据需要耗时多少秒？  
分析：数据规模扩大了，6倍 时间复杂度为O(n )，  
所以 6\*7 = 42s

3.假如有一个算法的时间复杂度是 O(n3)，并且已知该算法处理 1000 个数据需要耗时 7 秒中。请问，处理 6000 个数据需要耗时多少秒？  
分析：数据规模扩大了，6倍 时间复杂度为O(n3)，  
所以 63\*7 s

4.假如有一个算法的时间复杂度是 O(1)，并且已知该算法处理 1000 个数据需要耗时 7 秒中。请问，处理 6000 个数据需要耗时多少秒？  
分析：数据规模扩大了，6倍 时间复杂度为O(1)，  
所以1\*7 =7s

4.假如有一个算法的时间复杂度是 O(log(n))，并且已知该算法处理 1000 个数据需要耗时 7 秒中。请问，处理100 0000 个数据需要耗时多少秒？  
分析：数据规模扩大了，1000倍 时间复杂度为 O(log(n))，  
所以 log 2(1000\*1000) =log 2(1000)\+log 2(1000)=7+7=14s

## 时间复杂度的比较 ##

O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n2) <O(n3) <O(2n)…

# 空间复杂度 #

空间复杂度是对一个算法运行过程中，所需要的额外的空间大小（不包括自己本身消耗）。  
空间复杂度的计算基本规则也采用 大O渐进法

## 实例 ##

1：冒泡排序

冒泡排序是在自身的基础之上交换数组元素，只新定义了常数个变量，和N无关。所以空间复杂度为O(1)

2：阶乘递归

long factorial(int N) { 
    	return N < 2 ? N : factorial(N-1) * N;
    }

本题采用递归的方法，开辟的空间就造成了额外的空间，而且和N是有关系的（开辟N个空间），所以空间复杂度为 O(N)

3：斐波那契

int fibonacci(int N) { 
    	return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

本题采用递归的方法，开辟的空间就造成了额外的空间，而且和N是有关系的（开辟N个空间），所以空间复杂度为 O(N)  
（用完的空间还可以再次被使用，所以只需要开辟N个空间）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221023/35a8c61118ae44f88576cf5fd2b5b289.png