🧮 第4章 学习算法基础
📄 一句话概括

一个循环加一个数组,就能处理一年的账。 合计、平均、最大、最小,都是循环扫一遍,跑三遍和跑一遍同样是 O(n)。 切片是数组的另一个本事:不用循环,直接把一段拎出来。

📝 本章和前面几章的关系

上一篇的累加三件套是空转的,这一篇给它一批真数据。 教材用「一年的营业额」当例子,因为它够真实:十二个数,问四个指标。 这一篇还会把一维的问题抬到二维:每班一列分数,代码只多一层循环。

一、一年的账:十二个数

演示里摆了十二个月的营业额,从 1 月的 12 万到 12 月的 26 万。 要回答四个问题:全年合计多少、月均多少、哪个月最高、哪个月最低。 四个问题听着是四件事,其实是一件事:把这十二个数扫一遍,边扫边记。

这就是数组的价值——数据在手里整齐排着,问什么都只是换个记法。要是十二个数写成十二个变量, 每问一次都得重新列一遍加法。

二、三个数,三次循环

演示里算出来:全年合计 241 万,月均 20.08 万,最高是 11 月的 31 万,最低是 2 月的 9 万。 注意月均 20.08。241 除以 12 除不尽,小数位保留到哪儿是个口径问题,不是计算问题。 代码上是三次循环:求和一次,找最大一次,找最小一次。 看着笨,但每次都是 O(n)——数据再多一倍,也就多跑一遍。

这里第一次出现「复杂度」这个说法的实际含义: 不看跑了几遍,看每遍跟数据量什么关系。跑三遍固定次数的循环,还是 O(n)。

三、切片:不用循环也能拎一段

上半年、下半年各多少?演示里用切片一次拎出来:sales[:6] 和 sales[6:]。 上半年 96 万,下半年 145 万,差 +49 万——下半年明显更旺。 切片是数组独有的本事。链表做不到,因为它不知道「第 6 个在哪儿」,只能从头数过去。

这句话是第 3 章那条取舍的又一次落地:数组赢在「按下标取」,切片就是按下标取的高级版。 所以 2.5 说的「一起处理」,在 Python 里常常就是一行切片——不用写循环,因为它内部替你写了。

四、换个题:每班一列分数

同样是求总分和平均,但数据变成了三个班、每班三个人:这就是二维数组。 演示里一班 255 分(均 85.0),二班 223 分(均 74.3),三班 231 分(均 77.0)。 代码只多一层循环:外层走班级,内层走这个班里的三个人。

二维数组的全部用法,基本都是「外面套一层」。这句话能省掉很多死记硬背。 更重要的是它揭示了一个规律:数据结构变复杂,算法不一定变复杂。多一层维度,往往只多一层循环。

五、动手 Demo:十二个月的账,四个指标

把十二个月的营业额放进一个数组,求合计、月均、最高、最低。 再用切片分成上半年和下半年,看差多少。 最后换成二维数组:三个班、每班三人,求各班总分和平均。

sales = [12, 9, 15, 18, 22, 20, 17, 19, 24, 28, 31, 26]

print('全年合计', sum(sales), '万')
print('月均    ', round(sum(sales) / len(sales), 2), '万')
hi = sales.index(max(sales)) + 1
lo = sales.index(min(sales)) + 1
print('最高月份', hi, '月', max(sales), '万')
print('最低月份', lo, '月', min(sales), '万')

print('上半年', sum(sales[:6]), '下半年', sum(sales[6:]),
      '差', sum(sales[6:]) - sum(sales[:6]))

grid = [[80, 90, 85], [70, 75, 78], [77, 79, 75]]
for i, row in enumerate(grid, 1):
    print(i, '班 总分', sum(row), '平均', round(sum(row) / len(row), 1))

实跑输出:

--------------------------------------------------------------------
用数组处理大量数据:一年的账
--------------------------------------------------------------------


  ① 一年的营业额
  --------------------------------------------------------------------

| 月份 | 营业额 |
|---|---:|
| 1月 | 12 万 |
| 2月 | 9 万 |
| 3月 | 15 万 |
| 4月 | 18 万 |
| 5月 | 22 万 |
| 6月 | 20 万 |
| 7月 | 17 万 |
| 8月 | 19 万 |
| 9月 | 24 万 |
| 10月 | 28 万 |
| 11月 | 31 万 |
| 12月 | 26 万 |


  ② 三行代码,三个数
  --------------------------------------------------------------------
  全年合计:241 万
  月均    :20.08 万
  最高月份:11月(31 万)
  最低月份:2月(9 万)
  合计是一次循环,最高最低各一次。三次循环看着笨,但都是 O(n)——数据再多一倍,也就多跑一遍。

  ③ 加上半年下半年,一次变两次
  --------------------------------------------------------------------
  上半年:96 万,下半年:145 万,差 +49 万
  切片是数组的另一个用处:不用循环,直接把一段拎出来。
  上一节说的「一起处理」,在 Python 里常常就是切片一行。

  ④ 同样的套路换个题:班级总分
  --------------------------------------------------------------------

| 班级 | 三人总分 | 平均 |
|---|---:|---:|
| 一班 | 255 | 85.0 |
| 二班 | 223 | 74.3 |
| 三班 | 231 | 77.0 |

  把「一列数」换成「每班一列数」,代码只多一层循环。二维数组的全部用法,基本都是「外面套一层」。

①sales.index(max(sales)) 是「先找最大值,再问它在第几个」。 返回的下标从 0 起,所以加 1 才是月份。 ②月均那行用了 round(..., 2)。241 除以 12 是 20.0833…,保留两位是口径,不保留也照样对。 ③切片 sales[:6] 是前六个,sales[6:] 是后六个。含头不含尾,和 range 一个规矩。 ④二维那段 enumerate(grid, 1) 的第二个参数让下标从 1 开始,这样打出来是「1 班」而不是「0 班」。 这是 3.6 那个下标约定的实用例子。

30 秒实验

  1. 求「超过月均的月份有几个」,想想需要几层循环。
  2. 把二维数组改成「四个班、每班四人」,看代码要改哪里。
  3. 用切片求第三季度(7 到 9 月)的合计,下标该从几到几?

常见误区

  1. 「跑三遍循环比跑一遍慢三倍,所以该合并。」常数倍不影响 O(n),合并只在常数很大时才值得。
  2. 「切片会复制数据,所以不能用。」它确实复制一段,但只是这一段,不是整个数组。
  3. 「二维数组处理起来要写两层嵌套,太麻烦。」就是把一维的那套再套一层,逻辑一个字没变。
自测三问(点开对答案) 1. 求合计、平均、最大、最小,各要扫几遍数组? —— 各一遍,一共三到四遍。每遍都是 O(n),合并起来还是 O(n),常数倍不影响量级。 2. 上半年、下半年为什么一行就能分开? —— 切片。数组能按下标直接取一段,链表做不到。 3. 二维数组比一维多了什么? —— 多一层循环。外层走行,内层走这一行里的元素,算法本身没变。

合计和平均都会了。下一节换一类问题:这批数里谁最大、谁排第几。打擂台和排名,是两个新套路。

相关笔记