 和 O(log n) 详解)
算法复杂度 O(n) 和 O(log n) 详解基本概念算法复杂度是用来衡量算法执行效率的数学表示主要关注时间复杂度执行时间随输入规模增长的关系。O(n) - 线性时间复杂度含义算法的执行时间与输入规模n成正比关系输入规模增加一倍执行时间也大约增加一倍直观理解n 10 → 需要10次操作 n 100 → 需要100次操作 n 1000 → 需要1000次操作代码示例// O(n) 的典型例子遍历数组 public int findMax(int[] array) { int max array[0]; for (int i 1; i array.length; i) { // 循环n次 if (array[i] max) { max array[i]; } } return max; } // 另一个例子线性搜索 public boolean contains(int[] array, int target) { for (int num : array) { // 循环n次 if (num target) { return true; } } return false; }性能曲线时间 ↑ | / | / | / | / ---------→ 输入规模nO(log n) - 对数时间复杂度含义算法的执行时间与输入规模n的对数成正比输入规模指数级增长执行时间只线性增长O(log n) 通常指 log₂n二进制对数直观理解n 10 → 需要约3-4次操作 (log₂10 ≈ 3.32) n 100 → 需要约6-7次操作 (log₂100 ≈ 6.64) n 1000 → 需要约10次操作 (log₂1000 ≈ 9.97) n 1000000 → 需要约20次操作 (log₂1000000 ≈ 19.93)代码示例// O(log n) 的典型例子二分查找 public int binarySearch(int[] sortedArray, int target) { int left 0; int right sortedArray.length - 1; while (left right) { // 每次循环将搜索范围减半 int mid left (right - left) / 2; if (sortedArray[mid] target) { return mid; } else if (sortedArray[mid] target) { left mid 1; // 搜索右半部分 } else { right mid - 1; // 搜索左半部分 } } return -1; } // 另一个例子在二叉搜索树中查找 class TreeNode { int val; TreeNode left, right; } public TreeNode searchBST(TreeNode root, int target) { while (root ! null) { if (root.val target) { return root; } else if (target root.val) { root root.left; // 每次排除一半节点 } else { root root.right; } } return null; }性能曲线时间 ↑ | | ------ | / | / ---------→ 输入规模n (对数尺度)两者对比效率对比表输入规模nO(n) 操作次数O(log n) 操作次数效率差距1010~42.5倍100100~714倍1,0001,000~10100倍1,000,0001,000,000~2050,000倍实际场景对比// 假设有100万个元素的排序数组 int[] hugeArray new int[1_000_000]; // 已排序 // O(n) 线性搜索最坏需要100万次比较 long start System.nanoTime(); linearSearch(hugeArray, target); long linearTime System.nanoTime() - start; // O(log n) 二分查找最多需要20次比较 start System.nanoTime(); binarySearch(hugeArray, target); long binaryTime System.nanoTime() - start; System.out.println(O(n)时间: linearTime ns); System.out.println(O(log n)时间: binaryTime ns); System.out.println(效率提升: (linearTime / binaryTime) 倍);在HashMap红黑树中的应用回到之前的HashMap例子// 哈希冲突严重时 // JDK7: 使用链表 → O(n) 时间复杂度 // JDK8: 使用红黑树 → O(log n) 时间复杂度 // 假设某个桶中有1000个冲突元素 // 链表查找需要1000次比较 (O(n)) // 红黑树查找需要log₂(1000)≈10次比较 (O(log n))为什么这个优化很重要// 恶意攻击场景攻击者故意制造哈希碰撞 // 没有红黑树HashMap退化为链表性能急剧下降 // 有红黑树即使大量碰撞性能依然可接受 // 实际测试数据 // 10,000个冲突元素 // - 链表10,000次比较 // - 红黑树14次比较 (log₂10000 ≈ 13.3)常见复杂度等级从优到劣O(1)- 常数时间最优O(log n)- 对数时间优秀O(n)- 线性时间良好O(n log n)- 线性对数时间可接受O(n²)- 平方时间较差O(2ⁿ)- 指数时间极差总结核心要点✅O(n)执行时间与输入规模成正比适合小规模数据✅O(log n)执行时间增长远慢于输入规模增长适合大规模数据✅HashMap红黑树优化将最坏情况从O(n)提升到O(log n)显著提升性能实用建议处理大数据集时优先选择O(log n)算法小规模数据时O(n)算法可能更简单实用理解算法复杂度有助于写出更高效的代码public class AlgorithmComplexityDemo { // O(n) 的典型例子遍历数组 public static int findMax(int[] array) { int max array[0]; for (int i 1; i array.length; i) { // 循环n次 if (array[i] max) { max array[i]; } } return max; } // 另一个例子线性搜索 public static boolean contains(int[] array, int target) { for (int num : array) { // 循环n次 if (num target) { return true; } } return false; } // O(log n) 的典型例子二分查找 public static int binarySearch(int[] sortedArray, int target) { int left 0; int right sortedArray.length - 1; while (left right) { // 每次循环将搜索范围减半 int mid left (right - left) / 2; if (sortedArray[mid] target) { return mid; } else if (sortedArray[mid] target) { left mid 1; // 搜索右半部分 } else { right mid - 1; // 搜索左半部分 } } return -1; } // 另一个例子在二叉搜索树中查找 class TreeNode { int val; TreeNode left, right; } public TreeNode searchBST(TreeNode root, int target) { while (root ! null) { if (root.val target) { return root; } else if (target root.val) { root root.left; // 每次排除一半节点 } else { root root.right; } } return null; } public static void main(String[] args) { // test1(); mathLogTest(); } private static void mathLogTest() { // // 常用对数底数为10 // log₁₀100 2 // 因为 10² 100 // log₁₀1000 3 // 因为 10³ 1000 // log₁₀10 1 // 因为 10¹ 10 // //// 自然对数底数为e约等于2.718 // ln(e) 1 // 因为 e¹ e // //// 二进制对数底数为2计算机科学常用 // log₂8 3 // 因为 2³ 8 // log₂16 4 // 因为 2⁴ 16 // log₂1024 10 // 因为 2¹⁰ 1024 System.out.println(Math.log10(100));// 2.0 System.out.println(Math.log(4)/Math.log(2));// 2.0 // Math.log() 方法计算的是自然对数以 e 为底 System.out.println(Math.log(100)/Math.log(2));// 6.643856189774725 System.out.println(Math.log(4));// 1.3862943611198906 } private static void test1() { int n 10_000_000; int[] array new int[n]; for (int i 0; i n; i) { array[i] i; } long start System.nanoTime(); boolean contains contains(array, 580000); long end System.nanoTime(); long cost end - start; System.out.println(contains is: contains , Time used: cost); int i binarySearch(array, 580000); long end2 System.nanoTime(); long cost2 end2 - end; System.out.println(The index of 580000 is: i , Time used: cost2 , fast: (float) cost2 / cost); } }
