时间复杂度-关于 O(n) 和 O(log n)的定义

“O(n)” 和 “O(log n)” 是算法分析中的时间复杂度（Time Complexity）表示方式，用来衡量算法随着输入规模增大时，运行时间的增长趋势。我们来详细对比这两者：

---

🔢 O(n)（线性时间复杂度）

• 含义：随着输入数据量 n 的增加，算法的运行时间也线性增加。

• 举例：

  function sum(arr) {
    let total = 0;
    for (let i = 0; i < arr.length; i++) {
      total += arr[i];
    }
    return total;
  }
  

  这个函数会对每个元素做一次操作，所以时间复杂度是 O(n)。

• 特点：

  • 效率中等；
  • 适用于遍历型操作；
  • 如果 n = 1000，就需要大约 1000 次操作。

---

🪜 O(log n)（对数时间复杂度）

• 含义：随着 n 的增加，运行时间只增加对数倍数，增长非常慢。

• 举例：二分查找：

  function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
  
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] === target) return mid;
      if (arr[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
  
    return -1;
  }
  

  每次都将搜索区间减半，所以是 O(log n)。

• 特点：

  • 效率非常高；
  • 常见于排序数组上的查找、树结构操作（如平衡二叉树）；
  • 如果 n = 1024，最多只需要大约 log₂(1024) = 10 次操作！

---

⛳ 比较总结

时间复杂度	操作数增长	举例	效率
O(n)	成正比	遍历数组	中等
O(log n)	成对数增长	二分查找	非常高效

可视化对比（大致数量）：

n 值	O(n) 操作次数	O(log n) 操作次数
10	10	4
100	100	7
1000	1000	10
1,000,000	1,000,000	20

---