Java随笔-时间复杂度和空间复杂度

一、时间复杂度Time Complexity1.1 定义衡量算法执行时间随输入规模增长的变化趋势。不是实际运行时间受机器、编译器影响而是执行语句的次数。1.2 大 O 表示法规则只保留最高阶项忽略常数和低阶项。O(1) O(log n) O(n) O(n log n) O(n^2) O(n^3) O(2^n) O(n!)1.3 常见时间复杂度速查表时间复杂度名称示例O(1)常数时间数组随机访问、HashMap 查找O(log n)对数时间二分查找、二叉搜索树查找O(n)线性时间遍历数组、链表查找O(n log n)线性对数时间快速排序平均、归并排序、堆排序O(n^2)平方时间冒泡排序、选择排序、插入排序O(n^3)立方时间三重循环、矩阵乘法朴素算法O(2^n)指数时间递归斐波那契、子集问题O(n!)阶乘时间全排列、旅行商问题暴力1.4 计算口诀场景时间复杂度例子无循环、无递归O(1)数组随机访问arr[i]循环一次O(n)for (i0; in; i)循环嵌套O(n^2)两层 for 循环循环三层O(n^3)三层 for 循环循环变量乘除O(log n)for (i1; in; i*2)递归减半O(log n)二分查找递归分治O(n log n)归并排序、快速排序平均递归两个分支O(2^n)斐波那契递归全排列O(n!)排列组合问题1.5 计算示例// 示例 1O(1) - 常数时间intgetFirst(int[]arr){returnarr[0];// 执行 1 次与 n 无关}// 示例 2O(n) - 线性时间intsum(int[]arr){ints0;for(inti0;iarr.length;i){// 执行 n 次sarr[i];}returns;}// 示例 3O(n^2) - 平方时间voidbubbleSort(int[]arr){for(inti0;iarr.length;i){// n 次for(intj0;jarr.length-i-1;j){// 平均 n/2 次if(arr[j]arr[j1])swap(arr,j,j1);}}// 总次数 n * n/2 n^2/2 - 忽略常数 - O(n^2)}// 示例 4O(log n) - 对数时间intbinarySearch(int[]arr,inttarget){intleft0,rightarr.length-1;while(leftright){// 每次减半执行 log2(n) 次intmidleft(right-left)/2;if(arr[mid]target)returnmid;elseif(arr[mid]target)leftmid1;elserightmid-1;}return-1;}// 示例 5O(n log n) - 线性对数时间voidmergeSort(int[]arr,intleft,intright){if(leftright)return;intmidleft(right-left)/2;mergeSort(arr,left,mid);// T(n/2)mergeSort(arr,mid1,right);// T(n/2)merge(arr,left,mid,right);// O(n)// 递归式T(n) 2T(n/2) O(n) - 主定理 - O(n log n)}// 示例 6O(2^n) - 指数时间intfibonacci(intn){if(n1)returnn;returnfibonacci(n-1)fibonacci(n-2);// 两个分支递归树节点数 2^n}// 示例 7O(n!) - 阶乘时间voidpermute(int[]arr,intstart){if(startarr.length-1){print(arr);return;}for(intistart;iarr.length;i){// n 层递归每层 n, n-1, n-2...swap(arr,start,i);permute(arr,start1);swap(arr,start,i);}// 总排列数 n!每个排列生成需要 O(n) 时间}1.6 递归算法的时间复杂度分析递归树法// 斐波那契递归// fib(5)// / \// fib(4) fib(3)// / \ / \// fib(3) fib(2) fib(2) fib(1)// ...// 树高 n每层节点数翻倍 - 总节点数 2^n - O(2^n)主定理Master Theorem适用于分治递归T(n) aT(n/b) f(n)T(n) aT(n/b) O(n^c) 比较 c 与 log_b(a) - 若 c log_b(a) - T(n) O(n^(log_b(a))) - 若 c log_b(a) - T(n) O(n^c * log n) - 若 c log_b(a) - T(n) O(n^c)算法递归式abclog_b(a)结果二分查找T(n) T(n/2) O(1)1200O(log n)归并排序T(n) 2T(n/2) O(n)2211O(n log n)快速排序平均T(n) 2T(n/2) O(n)2211O(n log n)快速排序最坏T(n) T(n-1) O(n)----O(n^2)二、空间复杂度Space Complexity2.1 定义衡量算法执行过程中额外占用内存随输入规模增长的变化趋势。不包括输入数据本身占用的空间而是算法运行时的辅助空间。2.2 常见空间复杂度速查表空间复杂度名称示例O(1)常数空间交换两个数、原地排序O(log n)对数空间二分递归的调用栈O(n)线性空间复制数组、递归深度 nO(n^2)平方空间二维数组、矩阵运算O(n!)阶乘空间全排列的存储极少见2.3 计算规则场景空间复杂度例子只用几个变量O(1)交换两个数开辟与 n 相关的数组O(n)复制数组递归深度O(n)递归调用栈递归分治O(log n)二分递归二维数组O(n^2)矩阵运算递归树O(n) / O(log n)取决于递归深度2.4 计算示例// 示例 1O(1) 额外空间 - 原地操作voidswap(inta,intb){inttempa;// 只用 1 个额外变量ab;btemp;}// 示例 2O(n) 额外空间 - 复制数组int[]copyArray(int[]arr){int[]copynewint[arr.length];// 开辟 n 个空间for(inti0;iarr.length;i){copy[i]arr[i];}returncopy;}// 示例 3O(n) 递归栈空间 - 线性递归intfactorial(intn){if(n1)return1;returnn*factorial(n-1);// 递归深度 n每层一个栈帧}// 示例 4O(log n) 递归栈空间 - 二分递归intbinarySearch(int[]arr,intleft,intright,inttarget){if(leftright)return-1;intmidleft(right-left)/2;if(arr[mid]target)returnmid;elseif(arr[mid]target)returnbinarySearch(arr,mid1,right,target);// 深度 log nelsereturnbinarySearch(arr,left,mid-1,target);}// 示例 5原地排序 O(1) 额外空间voidquickSort(int[]arr,intleft,intright){if(leftright)return;intpivotpartition(arr,left,right);// 原地分区不开辟新数组quickSort(arr,left,pivot-1);quickSort(arr,pivot1,right);// 额外空间递归栈 O(log n)平均情况}// 示例 6归并排序 O(n) 额外空间voidmergeSort(int[]arr,intleft,intright){if(leftright)return;intmidleft(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);// 需要额外 O(n) 空间来合并两个有序数组int[]tempnewint[right-left1];// ... 合并逻辑}三、常见算法复杂度对照表算法时间复杂度平均时间复杂度最坏空间复杂度稳定性数组随机访问O(1)O(1)O(1)-数组顺序查找O(n)O(n)O(1)-二分查找O(log n)O(log n)O(1)-冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定希尔排序O(n log n)O(n^2)O(1)不稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(k)稳定桶排序O(n k)O(n^2)O(n k)稳定基数排序O(d(n k))O(d(n k))O(n k)稳定哈希表查找O(1)O(n)O(n)-二叉搜索树查找O(log n)O(n)O(n)-平衡二叉树查找O(log n)O(log n)O(n)-BFS/DFS图O(V E)O(V E)O(V)-Dijkstra堆优化O((V E) log V)O((V E) log V)O(V)-Floyd-WarshallO(V^3)O(V^3)O(V^2)-动态规划一维O(n)O(n)O(n)-动态规划二维O(n^2)O(n^2)O(n^2)-四、计算技巧4.1 时间复杂度计算步骤找循环几层循环就大概几阶注意循环变量的增量看递归画递归树看每层工作量和深度用主定理分治递归T(n) aT(n/b) f(n)4.2 空间复杂度计算步骤看额外数组有没有新开数组开多大看递归深度递归调用栈占多少层注意隐式空间比如 Java 中对象引用、String 拼接4.3 常见陷阱陷阱说明正确复杂度忽略递归栈空间递归的空间复杂度不是 O(1)看递归深度混淆输入空间和辅助空间空间复杂度不算输入数据本身只算额外空间平均 vs 最坏快速排序平均 O(n log n)最坏 O(n^2)通常说平均原地排序的栈空间快速排序原地但递归栈 O(log n)空间 O(log n)五、Android 开发中的实际考量// 例子 1加载图片列表// 时间复杂度 O(n)遍历 n 张图片// 空间复杂度 O(k)缓存 k 张图片LRUCache 控制// 例子 2RecyclerView 的 DiffUtil// 时间复杂度 O(n^2)Myers 差分算法最坏情况// 空间复杂度 O(n)需要额外的序列化空间// 例子 3深拷贝一个复杂对象// 时间复杂度 O(n)遍历所有节点// 空间复杂度 O(n)新对象占用的内存// 例子 4遍历 View 树// 时间复杂度 O(n)n 个 View 节点// 空间复杂度 O(h)h 为树高递归栈深度// 例子 5字符串拼接JavaStringresult;for(Strings:list){results;// 每次创建新 String 对象O(n^2) 时间}// 正确做法StringBuilderO(n) 时间O(n) 空间StringBuildersbnewStringBuilder();for(Strings:list){sb.append(s);}Stringresultsb.toString();六、总结维度关注点计算核心时间复杂度执行快慢语句执行次数看循环和递归空间复杂度内存占用额外辅助空间看数组和递归栈核心口诀时间复杂度看跑多快空间复杂度看用多少内存两者通常需要权衡。经典权衡案例场景时间优先空间优先查找哈希表 O(1) 时间O(n) 空间二分查找 O(log n) 时间O(1) 空间排序归并排序 O(n log n) 稳定O(n) 空间堆排序 O(n log n) 不稳定O(1) 空间最短路径Dijkstra 堆 O((VE)log V)Floyd O(V^3) 但代码简单字符串匹配KMP O(n) 时间O(m) 空间暴力 O(n*m) 时间O(1) 空间一句话时间换空间或空间换时间是算法设计的永恒主题。