时间复杂度与空间复杂度的详解
目录
1.时间复杂度
2.时间复杂度计算例题
3.空间复杂度
1.时间复杂度
算法中的基本操作的执行次数，为算法的时间复杂度。
如何表达 时间复杂度？
大O的渐进表示法
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要 大概执行次数，那么这里我们 使用大 O 的渐进表示法。
1、用常数1取代运行时间中的所有加法常数。2、在修改后的运行次数函数中，只保留最高阶项。3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
举例：
// 请计算一下 func1 基本操作执行了多少次？void func1 ( int N ){int count = 0 ;for ( int i = 0 ; i < N ; i ++ ) {for ( int j = 0 ; j < N ; j ++ ) {count ++ ;}}for ( int k = 0 ; k < 2 * N ; k ++ ) {count ++ ;}int M = 10 ;while (( M -- ) > 0 ) {count ++ ;}System . out . println ( count );}
题解：
Func1 执行的基本操作次数 ：F(N)=N^2+2*N+10;(1) 用常数1取代运行时间中的所有加法常数。F(N)=N^2+2*N+1；（2） 在修改后的运行次数函数中，只保留最高阶项。F(N)=N^2;=>O(N^2);
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数 ( 上界 )平均情况：任意输入规模的期望运行次数最好情况：任意输入规模的最小运行次数 ( 下界 )
在实际中一般情况关注的是算法的最坏运行情况，如：数组中搜索数据时间复杂度为 O(N)
O(N)中N表示问题的规模
2.时间复杂度计算例题
例题1：
// 计算 func2 的时间复杂度？void func2 ( int N , int M ) {int count = 0 ;for ( int k = 0 ; k < M ; k ++ ) {count ++ ;}for ( int k = 0 ; k < N ; k ++ ) {count ++ ;}System . out . println ( count );}
答案及分析：
基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
例题2：
// 计算 func3 的时间复杂度？void func3 （ int N ) {int count = 0 ;for ( int k = 0 ; k < 100 ; k ++ ) {count ++ ;}System . out . println ( count );}
答案及分析：
基本操作执行了100次，通过推导大O阶方法，时间复杂度为 O(1)
例题3：
// 计算 bubbleSort 的时间复杂度？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 ;}}}
答案及分析：
O(N)中N表示问题的规模
F(N)=N*(N-1)=N^2-N;
通过推导大 O 阶方法 + 时间复杂度一般看最坏，时间 复杂度为 O(N^2)
例题4：
// 计算 binarySearch 的时间复杂度？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 ;elsereturn mid ;}return - 1 ;}
答案及分析：
方法1：
对于不能直接看出的并较复杂的问题，可以采用数学归纳法
答案：
方法2：
N/(2^x) =1（x为循环的执行次数）
x的解：
例题 5
// 计算阶乘递归 factorial 的时间复杂度？long factorial ( int N ) {return N < 2 ? N : factorial ( N - 1 ) * N ;}
对于不能直接看出的并较复杂的问题，可以采用数学归纳法，但对于递归我们有专门总结的方法。
F（N）=递归的次数*每次递归代码的执行次数
答案及分析：
通过计算分析发现基本操作递归了 N次， 每次递归代码的执行次数为1 时间复杂度为O(N)
例题6：
// 计算斐波那契递归 fifibonacci 的时间复杂度？int fifibonacci ( int N ) {return N < 2 ? N : fifibonacci ( N - 1 ) + fifibonacci ( N - 2 );}
答案及分析：
对于不能直接看出的并较复杂的问题，可以采用数学归纳法（不展开）
面对这种多递归入口的题，可以使用补全法。
何为补全法？
以F4为例
F（N）：
1+2+4+……+2^(N-1)
=2^N-1;
O(2^N)
3.空间复杂度
空间复杂度是对一个算法在运行过程中 临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空 间，因为这个也没太大意义，所以空间复杂度算的是变量的个数
空间复杂度计算规则基本跟时间复杂度类似 ，也 使用大 O 渐进表示法 。
无论什么类型，只看开了多少的空间
例题1：
// 计算 bubbleSort 的空间复杂度？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 ;}}}
答案及分析：
使用了常数个额外空间，所以空间复杂度为 O(1)
例题2：
// 计算 fifibonacci 的空间复杂度？int [] fifibonacci ( int n ) {long [] fifibArray = new long [ n + 1 ];fifibArray [ 0 ] = 0 ;fifibArray [ 1 ] = 1 ;for ( int i = 2 ; i <= n ; i ++ ) {fifibArray [ i ] = fifibArray [ i - 1 ] + fifibArray [ i - 2 ];}return fifibArray ;}
答案及分析：
动态开辟了N个空间，空间复杂度为 O(N)
例题3：
// 计算阶乘递归 Factorial 的空间复杂度？long factorial ( int N ) {return N < 2 ? N : factorial ( N - 1 ) * N ;}
答案及分析：
递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)
以上为我个人的小分享，如有问题，欢迎讨论！！！
都看到这了，不如关注一下，给个免费的赞 
