1700507324
1700507325
1700507326
图11-1 电子计算器上的科学计数法
1700507327
1700507328
1700507329
1700507330
1700507331
用一个矩阵表示这个笛卡儿乘积的结果x2y1, x2y2, …, x2ym
1700507332
1700507333
1700507334
1700507335
1700507336
通过观察可以发现，在这样一个矩阵中，每个元素的和相当于整个矩阵的面积，也就是这样一个表达式
1700507337
1700507338
1700507339
1700507340
1700507341
与长和宽分别为n和m的矩形的面积公式
1700507342
1700507343
1700507344
1700507345
1700507346
相比。这种笛卡儿乘积同样是把正交的2个维度做了一种二重循环式的叠加，而且这种叠加在笛卡儿乘积中可以应用到多个正交维度——扩展到3个、4个或更多个维度。这种离散的视角在使用计算机解决问题的过程中非常普遍。在计算机中，建立包含很多描述对象的模型时也会用到这种视角。例如，在关系型数据库系统中，多个表之间使用JOIN连接，实际上相当于把一张一张的表看成一个一个独立的维度，进行JOIN的过程相当于在这种相乘之后的面积上进行谓词过滤或聚合操作（Group By）。
1700507347
1700507348
1700507349
1700507350
1700507351
数据科学家养成手册 [:1700503579]
1700507352
数据科学家养成手册 11.2 成本的度量
1700507353
1700507354
理想的算法要求计算结果“准确无误”。在模型的解空间中，如果元素是离散的，就通常是计算机擅长的范围。例如，经典的“八皇后问题”(4)就是要求出所有符合要求的解（如图11-2所示），不重、不漏、不错。在这种要求下，算法的优劣就只和处理的效率有关，也就是更快的算法更好。
1700507355
1700507356
1700507357
1700507358
1700507359
图11-2 八皇后问题的一组解
1700507360
1700507361
在算法领域对算法效率度量的描述方式记作O。用这个描述符号表示算法在处理对象的数量n变化的时候所产生的处理时间成本，称为时间复杂度。好的算法在处理数据时所花费的时间随着处理对象n的增加而线性增加，甚至会有比线性增加效率更高的方式；不好的算法则会在n增加时所花费时间呈指数级增加抑或更高。
1700507362
1700507363
常见的算法的时间复杂度有O(logn)、O(n)、O(2n)、O(n2)、O(nlogn)等（如图11-3所示）。
1700507364
1700507365
1700507366
1700507367
1700507368
图11-3 各种时间复杂度
1700507369
1700507370
例如，写一个从具有n个节点的单向链表（如图11-4所示）中找出某个确定值的算法，就需要遍历链表了。当这个查找对象在任何一个点上的概率均等的时候，平均查找次数是多少？这很容易计算：
1700507371
1700507372
1700507373