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
1700507374
1700507375
1700507376
1700507377
1700507378
图11-4 单向链表
1700507379
1700507380
也就是
1700507381
1700507382
1700507383
1700507384
1700507385
这种情况是和n成正比的，所以记作O(n)。
1700507386
1700507387
再如，在用平衡二叉树对某一确定值的数据进行查找的算法中，由于每次查找都会在访问一个树节点的时候“拐弯”，放弃对本层以下其他树节点及其子节点的查找，从而“最快”接近目标节点，而这种深入的次数只与层数有关，所以它的时间复杂度为
1700507388
1700507389
O(logn)