时间复杂度1. 时间复杂度概念时间复杂度的定义在计算机科学中算法的时间复杂度是⼀个数学函数它定量描述了该算法的运行时间。⼀个算法所花费的时间与其中语句的执行次数成正比例算法中的 基本操作的执行次数为算法的时间复杂度。2. 推到大O阶方法⽤常数1取代运行时间中的所有加法常数在修改后的运行次数函数中只保留最高阶项如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶3. 常见时间复杂度计算举例实例 1多重循环voidfunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}分析该方法的基本操作执行次数为F ( N ) N 2 2 ∗ N 10 F(N) N^2 2*N 10F(N)N22∗N10时间复杂度保留最高阶项后为O ( N 2 ) O(N^2)O(N2)实例 2单一输入规模的独立循环voidfunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}分析基本操作执行了2 N 10 2N 102N10次时间复杂度通过推导大O阶方法去掉相乘的常数后为O ( N ) O(N)O(N)实例 3多输入规模的独立循环voidfunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}System.out.println(count);}分析基本操作执行了M N M NMN次因为有两个未知数M MM和N NN时间复杂度O ( N M ) O(NM)O(NM)实例 4常数次循环voidfunc4(intN){intcount0;for(intk0;k100;k){count;}System.out.println(count);}分析基本操作执行了 100 次时间复杂度用常数1取代所有加法常数时间复杂度为O ( 1 ) O(1)O(1)实例 5冒泡排序voidbubbleSort(int[]array){for(intendarray.length;end0;end--){booleansortedtrue;for(inti1;iend;i){if(array[i-1]array[i]){Swap(array,i-1,i);sortedfalse;}}if(sortedtrue){break;}}}分析基本操作最好情况执行N NN次最坏情况执行了( N ∗ ( N − 1 ) ) / 2 (N*(N-1))/2(N∗(N−1))/2次时间复杂度实际中一般关注算法的最坏运行情况时间复杂度为O ( N 2 ) O(N^2)O(N2)实例 6二分查找intbinarySearch(int[]array,intvalue){intbegin0;intendarray.length-1;while(beginend){intmidbegin((end-begin)/2);if(array[mid]value)beginmid1;elseif(array[mid]value)endmid-1;elsereturnmid;}return-1;}分析基本操作最好情况执行 1 次因为每次二分查找排除掉一半的不适合值最坏情况执行log N \log NlogN次时间复杂度O ( log N ) O(\log N)O(logN)实例 7阶乘递归longfactorial(intN){returnN2?N:factorial(N-1)*N;}分析基本操作递归了N NN次时间复杂度O ( N ) O(N)O(N)实例 8斐波那契递归intfibonacci(intN){returnN2?N:fibonacci(N-1)fibonacci(N-2);}分析基本操作递归了2 N 2^N2N次时间复杂度O ( 2 N ) O(2^N)O(2N)空间复杂度1.概念空间复杂度是对⼀个算法在运⾏过程中临时占⽤存储空间⼤⼩的量度。空间复杂度计算规则基 本跟时间复杂度类似也使⽤⼤O渐进表⽰法。2.代码示例实例 1冒泡排序voidbubbleSort(int[]array){for(intendarray.length;end0;end--){booleansortedtrue;for(inti1;iend;i){if(array[i-1]array[i]){Swap(array,i-1,i);sortedfalse;}}if(sortedtrue){break;}}}空间复杂度分析由于算法在运行过程中只使用了常数个额外空间所以空间复杂度为O ( 1 ) O(1)O(1)实例 2动态数组解斐波那契数列int[]fibonacci(intn){long[]fibArraynewlong[n1];fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;// 注原返回类型与数组类型应一致此处保留原文档意图}空间复杂度分析因为算法内部动态开辟了N NN个空间所以空间复杂度为O ( N ) O(N)O(N)实例 3阶乘递归longfactorial(intN){returnN2?N:factorial(N-1)*N;}空间复杂度分析该算法递归调用了N NN次开辟了N NN个栈帧且每个栈帧使用了常数个空间因此空间复杂度为O ( N ) O(N)O(N)
