文章目录一、时间复杂度1. 什么是时间复杂度2. 大 O 表示法3.常见代码片段分析4.常见算法时间复杂度二、空间复杂度三、练习题1.消失的数字2.轮转数组一、时间复杂度1. 什么是时间复杂度时间复杂度用来描述随着输入规模 N 增大算法执行次数的增长趋势。2. 大 O 表示法假设某段代码的基本操作次数是F(N) N² 2N 10大 O 分析时只看增长趋势因此遵循三个规则。(1) 去掉常数项N² 2N 10其中 10 是常数项随着 N 增大影响很小可以忽略N² 2N(2) 只保留最高阶项当 N 很大时N² 的增长速度远大于 2N所以保留N²(3) 去掉最高阶项的系数如果是2N²仍然记作O(N²)所以F(N) N² 2N 10最终时间复杂度是O(N²)3.常见代码片段分析(1) 双层循环O(N²)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);}执行次数N² 2N 10其中双层循环执行 N * N N² 次单层循环执行 2N 次while 循环执行 10 次根据大 O 规则只保留最高阶项O(N²)(2) 单层循环O(N)voidfunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}执行次数2N 10去掉常数项和系数后O(N)(3) 两个独立变量O(N M)voidfunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}System.out.println(count);}第一个循环执行 M 次第二个循环执行 N 次。总执行次数N M所以时间复杂度是O(N M)注意如果 N 和 M 没有明确关系不能随便简化成 O(N) 或 O(M)。(4) 固定次数循环O(1)voidfunc4(intN){intcount0;for(intk0;k100;k){count;}System.out.println(count);}循环固定执行 100 次不会随着 N 增大而变化。所以时间复杂度是O(1)O(1) 不是只执行 1 次而是表示执行次数是常数级别。4.常见算法时间复杂度(1) 冒泡排序O(N²)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 - 1) (N - 2) (N - 3) … 1这是等差数列求和N(N - 1) / 2展开后1/2N² - 1/2N去掉低阶项和常数系数O(N²)这段代码带有 sorted 优化因此不同情况复杂度如下情况时间复杂度最好情况数组本身有序O(N)最坏情况数组逆序O(N²)平均情况O(N²)(2) 二分查找O(logN)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;}else{returnmid;}}return-1;}二分查找每次都会把查找范围缩小一半NN / 2N / 4N / 8…1假设执行了 x 次后规模缩小到 1N / 2^x 1得到2^x N所以x log₂N因此二分查找的时间复杂度是O(logN)在大 O 表示法中log 的底数通常不重要因为不同底数之间只差一个常数倍。(3) 阶乘递归O(N)// 计算阶乘递归factorial的时间复杂度longfactorial(intN){returnN2?N:factorial(N-1)*N;}递归调用过程factorial(N)factorial(N - 1)factorial(N - 2)…factorial(1)每次递归都让 N 减少 1所以递归调用次数约为 N 次。时间复杂度O(N)(4) 斐波那契递归O(2ᴺ)intfibonacci(intN){returnN2?N:fibonacci(N-1)fibonacci(N-2);}每次调用 fibonacci(N)都会继续调用fibonacci(N - 1)fibonacci(N - 2)递归会展开成一棵树存在大量重复计算。节点数量近似为2^0 2^1 2^2 … 2^(N - 1)等比数列求和后约为2^N - 1所以普通递归版斐波那契的时间复杂度通常记为O(2^N)二、空间复杂度空间复杂度用于衡量算法在运行过程中额外使用的存储空间随输入规模增长的变化趋势。常数额外空间O(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;}}}这段代码中额外使用的变量主要有end、sorted、i这些变量的数量是固定的不会随着数组长度 N 的增大而增加。所以冒泡排序的空间复杂度是O(1)线性额外空间O(N)示例用数组保存斐波那契数列int[]fibonacci(intn){int[]fibArraynewint[n1];fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;}这段代码内部新建了一个数组int[ ] fibArray new int[n 1];数组长度是 n 1会随着输入规模 n 的增大而增大。因此额外空间规模为n 1根据大 O 表示法忽略常数项后O(N)所以该算法的空间复杂度是O(N)注意如果只需要返回第 n 个斐波那契数而不是返回整个数组可以只用两个变量保存前两项intfibonacci(intn){if(n2){returnn;}intprev0;intcurr1;for(inti2;in;i){intnextprevcurr;prevcurr;currnext;}returncurr;}这时只使用固定数量的变量空间复杂度可以优化为O(1)递归空间复杂度看调用栈深度递归算法的空间复杂度不能只看代码里有没有创建数组还要看递归调用栈。递归阶乘O(N)示例longfactorial(intN){returnN2?N:factorial(N-1)*N;}调用过程大致如下factorial(N)factorial(N - 1)factorial(N - 2)…factorial(1)递归每次让 N 减少 1直到到达终止条件。所以最大递归深度约为N每一层递归只使用常数级空间因此总栈空间为N * O(1)所以空间复杂度是O(N)三、练习题1.消失的数字解法一: 求和法publicintmissingNumber(int[]nums){intnnums.length;// 1. 计算 0 到 n 的理想总和intexpectedSumn*(n1)/2;// 2. 计算数组中现有数字的实际总和intactualSum0;for(intnum:nums){actualSumnum;}// 3. 差值即为缺失值returnexpectedSum-actualSum;}时间复杂度代码只遍历了一次数组所以时间复杂度是O(n)空间复杂度只使用了几个变量n、expectSum、actualSum所以空间复杂度是O(1)解法二: 异或法如果把 0 ~ n 和数组中的所有数字全部异或出现两次的数字会相互抵消最后剩下的就是缺失的数字。classSolution{publicintmissingNumber(int[]nums){intx0;for(inti0;inums.length;i){x^i;}for(intnum:nums){x^num;}returnx;}}复杂度同样是时间复杂度O(n)空间复杂度O(1)2.轮转数组classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;k%n;// 步骤1防止 k 大于数组长度// 步骤2翻转整个数组reverse(nums,0,n-1);// 步骤3翻转前 k 个元素reverse(nums,0,k-1);// 步骤4翻转后面剩余的元素reverse(nums,k,n-1);}// 辅助函数翻转数组中从 start 到 end 的部分privatevoidreverse(int[]nums,intstart,intend){while(startend){inttempnums[start];nums[start]nums[end];nums[end]temp;start;end--;}}}时间复杂度三次翻转每个元素最多被交换常数次。O(n)空间复杂度只使用了几个变量n、k、start、end、temp所以空间复杂度是O(1) 轻松学数据结构之 复杂度
文章目录一、时间复杂度1. 什么是时间复杂度2. 大 O 表示法3.常见代码片段分析4.常见算法时间复杂度二、空间复杂度三、练习题1.消失的数字2.轮转数组一、时间复杂度1. 什么是时间复杂度时间复杂度用来描述随着输入规模 N 增大算法执行次数的增长趋势。2. 大 O 表示法假设某段代码的基本操作次数是F(N) N² 2N 10大 O 分析时只看增长趋势因此遵循三个规则。(1) 去掉常数项N² 2N 10其中 10 是常数项随着 N 增大影响很小可以忽略N² 2N(2) 只保留最高阶项当 N 很大时N² 的增长速度远大于 2N所以保留N²(3) 去掉最高阶项的系数如果是2N²仍然记作O(N²)所以F(N) N² 2N 10最终时间复杂度是O(N²)3.常见代码片段分析(1) 双层循环O(N²)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);}执行次数N² 2N 10其中双层循环执行 N * N N² 次单层循环执行 2N 次while 循环执行 10 次根据大 O 规则只保留最高阶项O(N²)(2) 单层循环O(N)voidfunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}执行次数2N 10去掉常数项和系数后O(N)(3) 两个独立变量O(N M)voidfunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}System.out.println(count);}第一个循环执行 M 次第二个循环执行 N 次。总执行次数N M所以时间复杂度是O(N M)注意如果 N 和 M 没有明确关系不能随便简化成 O(N) 或 O(M)。(4) 固定次数循环O(1)voidfunc4(intN){intcount0;for(intk0;k100;k){count;}System.out.println(count);}循环固定执行 100 次不会随着 N 增大而变化。所以时间复杂度是O(1)O(1) 不是只执行 1 次而是表示执行次数是常数级别。4.常见算法时间复杂度(1) 冒泡排序O(N²)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 - 1) (N - 2) (N - 3) … 1这是等差数列求和N(N - 1) / 2展开后1/2N² - 1/2N去掉低阶项和常数系数O(N²)这段代码带有 sorted 优化因此不同情况复杂度如下情况时间复杂度最好情况数组本身有序O(N)最坏情况数组逆序O(N²)平均情况O(N²)(2) 二分查找O(logN)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;}else{returnmid;}}return-1;}二分查找每次都会把查找范围缩小一半NN / 2N / 4N / 8…1假设执行了 x 次后规模缩小到 1N / 2^x 1得到2^x N所以x log₂N因此二分查找的时间复杂度是O(logN)在大 O 表示法中log 的底数通常不重要因为不同底数之间只差一个常数倍。(3) 阶乘递归O(N)// 计算阶乘递归factorial的时间复杂度longfactorial(intN){returnN2?N:factorial(N-1)*N;}递归调用过程factorial(N)factorial(N - 1)factorial(N - 2)…factorial(1)每次递归都让 N 减少 1所以递归调用次数约为 N 次。时间复杂度O(N)(4) 斐波那契递归O(2ᴺ)intfibonacci(intN){returnN2?N:fibonacci(N-1)fibonacci(N-2);}每次调用 fibonacci(N)都会继续调用fibonacci(N - 1)fibonacci(N - 2)递归会展开成一棵树存在大量重复计算。节点数量近似为2^0 2^1 2^2 … 2^(N - 1)等比数列求和后约为2^N - 1所以普通递归版斐波那契的时间复杂度通常记为O(2^N)二、空间复杂度空间复杂度用于衡量算法在运行过程中额外使用的存储空间随输入规模增长的变化趋势。常数额外空间O(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;}}}这段代码中额外使用的变量主要有end、sorted、i这些变量的数量是固定的不会随着数组长度 N 的增大而增加。所以冒泡排序的空间复杂度是O(1)线性额外空间O(N)示例用数组保存斐波那契数列int[]fibonacci(intn){int[]fibArraynewint[n1];fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;}这段代码内部新建了一个数组int[ ] fibArray new int[n 1];数组长度是 n 1会随着输入规模 n 的增大而增大。因此额外空间规模为n 1根据大 O 表示法忽略常数项后O(N)所以该算法的空间复杂度是O(N)注意如果只需要返回第 n 个斐波那契数而不是返回整个数组可以只用两个变量保存前两项intfibonacci(intn){if(n2){returnn;}intprev0;intcurr1;for(inti2;in;i){intnextprevcurr;prevcurr;currnext;}returncurr;}这时只使用固定数量的变量空间复杂度可以优化为O(1)递归空间复杂度看调用栈深度递归算法的空间复杂度不能只看代码里有没有创建数组还要看递归调用栈。递归阶乘O(N)示例longfactorial(intN){returnN2?N:factorial(N-1)*N;}调用过程大致如下factorial(N)factorial(N - 1)factorial(N - 2)…factorial(1)递归每次让 N 减少 1直到到达终止条件。所以最大递归深度约为N每一层递归只使用常数级空间因此总栈空间为N * O(1)所以空间复杂度是O(N)三、练习题1.消失的数字解法一: 求和法publicintmissingNumber(int[]nums){intnnums.length;// 1. 计算 0 到 n 的理想总和intexpectedSumn*(n1)/2;// 2. 计算数组中现有数字的实际总和intactualSum0;for(intnum:nums){actualSumnum;}// 3. 差值即为缺失值returnexpectedSum-actualSum;}时间复杂度代码只遍历了一次数组所以时间复杂度是O(n)空间复杂度只使用了几个变量n、expectSum、actualSum所以空间复杂度是O(1)解法二: 异或法如果把 0 ~ n 和数组中的所有数字全部异或出现两次的数字会相互抵消最后剩下的就是缺失的数字。classSolution{publicintmissingNumber(int[]nums){intx0;for(inti0;inums.length;i){x^i;}for(intnum:nums){x^num;}returnx;}}复杂度同样是时间复杂度O(n)空间复杂度O(1)2.轮转数组classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;k%n;// 步骤1防止 k 大于数组长度// 步骤2翻转整个数组reverse(nums,0,n-1);// 步骤3翻转前 k 个元素reverse(nums,0,k-1);// 步骤4翻转后面剩余的元素reverse(nums,k,n-1);}// 辅助函数翻转数组中从 start 到 end 的部分privatevoidreverse(int[]nums,intstart,intend){while(startend){inttempnums[start];nums[start]nums[end];nums[end]temp;start;end--;}}}时间复杂度三次翻转每个元素最多被交换常数次。O(n)空间复杂度只使用了几个变量n、k、start、end、temp所以空间复杂度是O(1)