《图解算法》

[goldEli]

Go Back

[goldEli]

二分法（Binary Search）

从有序数组中，快速找到某一项的位置，如果是遍历每一项的的话，时间复杂度就是O(n)。

如果取中间数比较大小，就可以过滤一半无用的数据，这样复杂度就会变成 logn。（log 就是对数，比如2^3 = 8，那么log8 = 3）

比如长度为8的数组 [1,3,5,6,8,12,32,71]，用二分法找到 32 的位置：

arr = [1,3,5,6,8,12,32,71]
target = 32

def brinary_search(arr, target):
  start = 0
  end = len(arr) - 1
  mid = int((start + end) / 2)

  while mid < len(arr) or mid > -1:
    mid = int((start + end) / 2)
    guess = arr[mid]
    if guess == target:
      return mid
    if guess > target:
      end = mid - 1
    elif guess < target:
      start = mid + 1
  return None

print(brinary_search(arr, target)) # 6

[goldEli]

时间复杂度如何计算？

• 时间复杂度不表示运行时长
• 时间复杂度只表示操作次数，而且是可能的最大的操作次数
• 用 O 表示，O 表示 operation 操作
• 常见的的时间复杂度：O(logn) 、O(n)、O(n^2)、O(n!)
  • 比如说普通查询，如果个数为n，需要对n进行挨个遍历，那么复杂度就为 O(n)
  • 二分查询复杂度就为O(logn)
  • 如果你的算法要用到双循环那么你的复杂度就为O(n^2)
  • 假如你计划去五个城市，找到去个城市最短的路径，那么你需要计算 54321，这就叫阶乘，复杂度为O(n!)