尧图网站建设 
时间复杂度评估算法运行需要多少时间空间复杂度评估算法运行需要占用多少内存。两者都只关心【数据规模变大时】的增长趋势不统计精确耗时 / 内存大小。时间复杂度算循环多少次空间复杂度算新开多少内存一、时间复杂度 O (f (n))n输入数据的规模比如数组长度 \(O()\)大 O 记号表示最坏情况下算法执行步数随 n 的增长量级忽略常数、低次项。常见复杂度从快到慢(O(1)) 常数阶执行次数固定和 n 无关int a arr[0]; // 不管数组多大只取第一个元素(O(log n)) 对数阶每次处理把问题规模减半二分查找(O(n)) 线性阶循环遍历一遍数据for(int i0; in; i){}(O(nlog n))线性对数阶快速排序、归并排序(O(n^2)) 平方阶两层嵌套循环for(int i0;in;i){ for(int j0;jn;j){} }(O(n^3)) 立方阶三层循环(O(2^n)) 指数阶、(O(n!)) 阶乘阶数据稍微大一点就直接算不完基本不可用✅ 重点只看最高阶项去掉系数。例(2n^23n5) → (O(n^2))默认分析最坏时间复杂度二、空间复杂度 O (f (n))衡量算法额外申请的内存空间随数据规模 n 的增长趋势。 ⚠️输入本身占用的空间不算只算算法执行过程中新开辟的变量、数组、递归栈等。例子(O(1)) 常数空间只定义几个临时变量没有开辟随 n 变大的容器int sum 0; for(int i0;in;i) sum arr[i];(O(n))新创建长度为 n 的数组int[] newArr new int[n];递归递归深度决定空间复杂度。比如递归深度为 n则空间复杂度 \(O(n)\)常见概念原地算法in-place一般指空间复杂度 \(O(1)\)不需要额外大量存储空间。三、举个直观对比例子给定长度为 n 的数组求数组最大值int max arr[0]; for(int i1; in; i){ if(arr[i] max) max arr[i]; }时间复杂度\(O(n)\)遍历一次数组空间复杂度\(O(1)\)只额外开了 max 变量四、面试常问要点为什么不用毫秒统计运行时间代码运行时间受 CPU、语言、环境影响。复杂度是算法本身的理论特性和机器无关用来比较算法优劣。时间和空间经常可以取舍空间换时间缓存哈希表。大 O 只看增长趋势\(n10\) 的时候 \(O(n^2)\) 可能比 \(O(n)\) 还快只有 n 很大的时候复杂度差异才会体现。Java 集合常用操作时间 空间复杂度说明均为平均情况标注最坏n代表集合内元素数量只看核心操作增、删、查空间复杂度指集合本身存储元素的空间新增元素时底层扩容会有额外开销临时操作一般是 O (1)一、List 列表ArrayList数组实现随机访问强操作时间复杂度说明get(index)O(1)直接数组下标访问set(index)O(1)修改指定下标add (末尾)O (1) 平均O (n) 最坏扩容时需要复制整个数组add (中间 / 头部)O(n)后面元素全部后移remove(index)O(n)删除点之后元素全部前移contains()O(n)需要遍历查找空间底层数组容量 ≥ 元素个数空间复杂度 O (n)LinkedList双向链表操作时间复杂度说明get(index)O(n)需要从头 / 尾遍历到下标add (首尾)O(1)链表节点修改指针add (中间)O(n)先要遍历找到位置remove (首尾)O(1)remove (中间)O(n)先遍历定位contains()O(n)遍历查找⚠️ 很多人误区LinkedList 不是所有 add/remove 都是 O (1)只有头尾操作才是 O (1)空间O (n)每个节点额外存前后指针内存开销比 ArrayList 大二、Set 集合不重复HashSet底层 HashMap操作时间复杂度addO (1) 平均O (n) 最坏哈希大量冲突removeO (1) 平均O (n) 最坏containsO (1) 平均O (n) 最坏TreeSet底层 TreeMap红黑树有序操作时间复杂度add / remove / contains\(O(\log n)\)红黑树元素自动排序支持范围查找LinkedHashSet继承 HashSet额外维护插入顺序增删查平均 O (1)空间HashSet / TreeSet 都是 O (n)三、Map 键值对HashMap面试重点数组 链表 / 红黑树JDK1.8操作时间复杂度get(key)O (1) 平均最坏 O (n)哈希冲突严重链表put(key,val)O (1) 平均最坏 O (n)扩容时 O (n)remove(key)O (1) 平均最坏 O (n)JDK1.8链表长度≥8 转红黑树此时最坏退化成 \(O(\log n)\)TreeMap红黑树key 有序操作时间复杂度put / get / remove\(O(\log n)\)LinkedHashMap底层 HashMap 双向链表保留插入顺序增删查平均 O (1)空间HashMap / TreeMap O (n)四、Queue / DequeArrayDeque数组双端队列推荐替代 Stack、LinkedList 做队列addFirst/addLast、pollFirst/pollLast平均 O (1)扩容时 O (n)PriorityQueue 优先队列最小堆offer / poll\(O(\log n)\)peekO(1)containsO(n)✅ 总结ArrayList随机访问 O (1)中间插入删除 O (n)LinkedList头尾增删 O (1)按下标查找 O (n)HashMap增删查平均 O (1)TreeMap 固定 \(O(\log n)\)HashSet 等价 HashMapTreeSet 等价 TreeMapPriorityQueue 入队出队都是 \(O(\log n)\) 时间复杂度 空间复杂度
时间复杂度评估算法运行需要多少时间空间复杂度评估算法运行需要占用多少内存。两者都只关心【数据规模变大时】的增长趋势不统计精确耗时 / 内存大小。时间复杂度算循环多少次空间复杂度算新开多少内存一、时间复杂度 O (f (n))n输入数据的规模比如数组长度 \(O()\)大 O 记号表示最坏情况下算法执行步数随 n 的增长量级忽略常数、低次项。常见复杂度从快到慢(O(1)) 常数阶执行次数固定和 n 无关int a arr[0]; // 不管数组多大只取第一个元素(O(log n)) 对数阶每次处理把问题规模减半二分查找(O(n)) 线性阶循环遍历一遍数据for(int i0; in; i){}(O(nlog n))线性对数阶快速排序、归并排序(O(n^2)) 平方阶两层嵌套循环for(int i0;in;i){ for(int j0;jn;j){} }(O(n^3)) 立方阶三层循环(O(2^n)) 指数阶、(O(n!)) 阶乘阶数据稍微大一点就直接算不完基本不可用✅ 重点只看最高阶项去掉系数。例(2n^23n5) → (O(n^2))默认分析最坏时间复杂度二、空间复杂度 O (f (n))衡量算法额外申请的内存空间随数据规模 n 的增长趋势。 ⚠️输入本身占用的空间不算只算算法执行过程中新开辟的变量、数组、递归栈等。例子(O(1)) 常数空间只定义几个临时变量没有开辟随 n 变大的容器int sum 0; for(int i0;in;i) sum arr[i];(O(n))新创建长度为 n 的数组int[] newArr new int[n];递归递归深度决定空间复杂度。比如递归深度为 n则空间复杂度 \(O(n)\)常见概念原地算法in-place一般指空间复杂度 \(O(1)\)不需要额外大量存储空间。三、举个直观对比例子给定长度为 n 的数组求数组最大值int max arr[0]; for(int i1; in; i){ if(arr[i] max) max arr[i]; }时间复杂度\(O(n)\)遍历一次数组空间复杂度\(O(1)\)只额外开了 max 变量四、面试常问要点为什么不用毫秒统计运行时间代码运行时间受 CPU、语言、环境影响。复杂度是算法本身的理论特性和机器无关用来比较算法优劣。时间和空间经常可以取舍空间换时间缓存哈希表。大 O 只看增长趋势\(n10\) 的时候 \(O(n^2)\) 可能比 \(O(n)\) 还快只有 n 很大的时候复杂度差异才会体现。Java 集合常用操作时间 空间复杂度说明均为平均情况标注最坏n代表集合内元素数量只看核心操作增、删、查空间复杂度指集合本身存储元素的空间新增元素时底层扩容会有额外开销临时操作一般是 O (1)一、List 列表ArrayList数组实现随机访问强操作时间复杂度说明get(index)O(1)直接数组下标访问set(index)O(1)修改指定下标add (末尾)O (1) 平均O (n) 最坏扩容时需要复制整个数组add (中间 / 头部)O(n)后面元素全部后移remove(index)O(n)删除点之后元素全部前移contains()O(n)需要遍历查找空间底层数组容量 ≥ 元素个数空间复杂度 O (n)LinkedList双向链表操作时间复杂度说明get(index)O(n)需要从头 / 尾遍历到下标add (首尾)O(1)链表节点修改指针add (中间)O(n)先要遍历找到位置remove (首尾)O(1)remove (中间)O(n)先遍历定位contains()O(n)遍历查找⚠️ 很多人误区LinkedList 不是所有 add/remove 都是 O (1)只有头尾操作才是 O (1)空间O (n)每个节点额外存前后指针内存开销比 ArrayList 大二、Set 集合不重复HashSet底层 HashMap操作时间复杂度addO (1) 平均O (n) 最坏哈希大量冲突removeO (1) 平均O (n) 最坏containsO (1) 平均O (n) 最坏TreeSet底层 TreeMap红黑树有序操作时间复杂度add / remove / contains\(O(\log n)\)红黑树元素自动排序支持范围查找LinkedHashSet继承 HashSet额外维护插入顺序增删查平均 O (1)空间HashSet / TreeSet 都是 O (n)三、Map 键值对HashMap面试重点数组 链表 / 红黑树JDK1.8操作时间复杂度get(key)O (1) 平均最坏 O (n)哈希冲突严重链表put(key,val)O (1) 平均最坏 O (n)扩容时 O (n)remove(key)O (1) 平均最坏 O (n)JDK1.8链表长度≥8 转红黑树此时最坏退化成 \(O(\log n)\)TreeMap红黑树key 有序操作时间复杂度put / get / remove\(O(\log n)\)LinkedHashMap底层 HashMap 双向链表保留插入顺序增删查平均 O (1)空间HashMap / TreeMap O (n)四、Queue / DequeArrayDeque数组双端队列推荐替代 Stack、LinkedList 做队列addFirst/addLast、pollFirst/pollLast平均 O (1)扩容时 O (n)PriorityQueue 优先队列最小堆offer / poll\(O(\log n)\)peekO(1)containsO(n)✅ 总结ArrayList随机访问 O (1)中间插入删除 O (n)LinkedList头尾增删 O (1)按下标查找 O (n)HashMap增删查平均 O (1)TreeMap 固定 \(O(\log n)\)HashSet 等价 HashMapTreeSet 等价 TreeMapPriorityQueue 入队出队都是 \(O(\log n)\)