• 评价算法的好坏：渐近时间复杂度和渐近空间复杂度。

• 渐近时间复杂度的大O标记：

  • - 常量时间复杂度 - 布隆过滤器 / 哈希存储
  • - 对数时间复杂度 - 折半查找（二分查找）
  • - 线性时间复杂度 - 顺序查找 / 计数排序
  • - 对数线性时间复杂度 - 高级排序算法（归并排序、快速排序）
  • - 平方时间复杂度 - 简单排序算法（选择排序、插入排序、冒泡排序）
  • - 立方时间复杂度 - Floyd算法 / 矩阵乘法运算
  • - 几何级数时间复杂度 - 汉诺塔
  • - 阶乘时间复杂度 - 旅行经销商问题 - NPC

  

• 排序算法（选择、冒泡和归并）和查找算法（顺序和折半）

      """冒泡排序"""
      items = items[:]
      for i in range(len(items) - 1):
          swapped = False
          for j in range(len(items) - 1 - i):
              if comp(items[j], items[j + 1]):
                  items[j], items[j + 1] = items[j + 1], items[j]
                  swapped = True
          if not swapped:
              break
      return items

  def bubble_sort(items, comp=lambda x, y: x > y):
      """搅拌排序(冒泡排序升级版)"""
      items = items[:]
      for i in range(len(items) - 1):
          swapped = False
          for j in range(len(items) - 1 - i):
              if comp(items[j], items[j + 1]):
                  items[j], items[j + 1] = items[j + 1], items[j]
                  swapped = True
          if swapped:
              swapped = False
              for j in range(len(items) - 2 - i, i, -1):
                  if comp(items[j - 1], items[j]):
                      items[j], items[j - 1] = items[j - 1], items[j]
                      swapped = True
              break
      return items

  ```Python def merge(items1, items2, comp=lambda x, y: x < y):

def merge_sort(items, comp=lambda x, y: x < y): return _merge_sort(list(items), comp)

def _merge_sort(items, comp): “””归并排序””” if len(items) < 2: return items mid = len(items) // 2 left = _merge_sort(items[:mid], comp) right = _merge_sort(items[mid:], comp) return merge(left, right, comp)

  ```Python
  def seq_search(items, key):
      for index, item in enumerate(items):
          if item == key:
              return index
      return -1

  def bin_search(items, key):
      """折半查找"""
      start, end = 0, len(items) - 1
      while start <= end:
          mid = (start + end) // 2
          if key > items[mid]:
              start = mid + 1
          elif key < items[mid]:
              end = mid - 1
          else:
              return mid
      return -1

• • 穷举法 - 又称为暴力破解法，对所有的可能性进行验证，直到找到正确答案。
  • 贪婪法 - 在对问题求解时，总是做出在当前看来
  • 最好的选择，不追求最优解，快速找到满意解。
  • 分治法 - 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到可以直接求解的程度，最后将子问题的解进行合并得到原问题的解。
  • 回溯法 - 回溯法又称为试探法，按选优条件向前搜索，当搜索到某一步发现原先选择并不优或达不到目标时，就退回一步重新选择。
  • 动态规划 - 基本思想也是将待求解问题分解成若干个子问题，先求解并保存这些子问题的解，避免产生大量的重复运算。

  穷举法例子：百钱百鸡和五人分鱼。

  贪婪法例子：假设小偷有一个背包，最多能装20公斤赃物，他闯入一户人家，发现如下表所示的物品。很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。

  | 名称 | 价格（美元） | 重量（kg） | | :——: | :—————: | :————: | | 电脑 | 200 | 20 | | 收音机 | 20 | 4 | | 钟 | 175 | 10 | | 花瓶 | 50 | 2 | | 书 | 10 | 1 | | 油画 | 90 | 9 |

  ```Python “”” 贪婪法：在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。 输入： 20 6 电脑 200 20 收音机 20 4 钟 175 10 花瓶 50 2 书 10 1 油画 90 9 “”” class Thing(object):

  """物品"""
  def __init__(self, name, price, weight):
      self.name = name
      self.price = price
      self.weight = weight
  @property
  def value(self):
      """价格重量比"""

def input_thing(): “””输入物品信息””” name_str, price_str, weight_str = input().split() return name_str, int(price_str), int(weight_str)

def main(): “””主函数””” maxweight, num_of_things = map(int, input().split()) all_things = [] for in range(num_of_things): all_things.append(Thing(*input_thing())) all_things.sort(key=lambda x: x.value, reverse=True) total_weight = 0 total_price = 0 for thing in all_things: if total_weight + thing.weight <= max_weight: print(f’小偷拿走了{thing.name}’) total_weight += thing.weight total_price += thing.price print(f’总价值: {total_price}美元’)

if name == ‘main‘: main()

  分治法例子：[快速排序](https://zh.wikipedia.org/zh/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F)。
  ```Python
  """
  """
  def quick_sort(items, comp=lambda x, y: x <= y):
      items = list(items)[:]
      _quick_sort(items, 0, len(items) - 1, comp)
      return items
  def _quick_sort(items, start, end, comp):
      if start < end:
          pos = _partition(items, start, end, comp)
          _quick_sort(items, start, pos - 1, comp)
          _quick_sort(items, pos + 1, end, comp)
  def _partition(items, start, end, comp):
      pivot = items[end]
      i = start - 1
      for j in range(start, end):
          if comp(items[j], pivot):
              i += 1
              items[i], items[j] = items[j], items[i]
      items[i + 1], items[end] = items[end], items[i + 1]
      return i + 1

回溯法例子：。

  def main():
      items = list(map(int, input().split()))
      overall = partial = items[0]
      for i in range(1, len(items)):
          partial = max(items[i], partial + items[i])
          overall = max(partial, overall)
      print(overall)

说明：这个题目最容易想到的解法是使用二重循环，但是代码的时间性能将会变得非常的糟糕。使用动态规划的思想，仅仅是多用了两个变量，就将原来$O(N^2)$复杂度的问题变成了$O(N)$。