小结

  • 算法分析是一种独立于实现的算法度量方法。

  • 大 O 记法使得算法可以根据随问题规模增长而起主导作用的部分进行归类。

讨论题

  1. 给出以下代码的大 O 性能。

    for i in range(n):
  for j in range(n):
        k = 2 + 2

  2. 给出以下代码的大 O 性能。

    for i in range(n):
  k = 2 + 2

  3. 给出以下代码的大 O 性能。

    i = n
while i > 0:
  k = 2 + 2
  i = i // 2

  4. 给出以下代码的大 O 性能。

    for i in range(n):
  for j in range(n):
        for k in range(n):
                k = 2 + 2

  5. 给出以下代码的大 O 性能。

    i = n
while i > 0:
  k = 2 + 2
  i = i // 2

  6. 给出以下代码的大 O 性能。

    for i in range(n):
  k = 2 + 2
for j in range(n):
  k = 2 + 2
for k in range(n):
  k = 2 + 2

编程练习

  1. 设计一个实验，证明列表的索引操作为常数阶。

  2. 设计一个实验，证明字典的取值操作和赋值操作为常数阶。

  3. 设计一个实验，针对列表和字典比较 del 操作的性能。

  4. 给定一个数字列表，其中的数字随机排列，编写一个线性阶算法，找出第 k 小的元素，并解释为何该算法的阶是线性的。

  5. 针对前一个练习，能将算法的时间复杂度优化到 \$O(n log n)\$ 吗？