1700507460
1700507461
表11-3 N皇后求解盘面宽度为N与N-1时的单次试探时间比
1700507462
1700507463
盘面宽 b单次试探时间（秒） 盘面宽度为N与N-1时的单次试探时间比 9 1.9875E-10 0.144977364 10 3.16E-11 0.158993344 11 6.01798E-12 0.190442413 12 1.14232E-12 0.189817095 13 2.08908E-13 0.182881075 14 3.94674E-14 0.188922486 这就表明，N每增加1，平均每次试探的时间就会变为之前的0.18倍左右（如图11-9所示）。这样我们可以猜测：当N=15时，单次的平均时间可能还会继续以这个比例下降。
1700507464
1700507465
1700507466
1700507467
1700507468
图11-9 盘面宽度为N与N – 1时的单次试探时间比
1700507469
1700507470
N=15的情况如下。
1700507471
1700507472
[root@ann science]# time python eight.py 15total test:437893890380859375; total solution:2279184 real 52m46.628suser 52m46.265ssys 0m0.094s
1700507473
1700507474
计算结果如表11-4所示。可以看出，平均单次试探时间下降为前一次的0.18倍左右。
1700507475
1700507476
表11-4 N皇后问题求解时间（N=15）
1700507477
1700507478
1700507479
1700507480
1700507481
在这个例子中我们发现了一个现象：虽然时间复杂度是O(nn)，但是花费的时间并非如此。在测量中也发现：单次试探的时间每次下降为之前的0.18倍左右。也就是说，当N=15时，我们还没有找出这条渐近线的极限。没关系，下面这两个结论已经很重要了。
1700507482
1700507483
结论1：时间复杂度的增加和实际运算的时间增加不成比例
1700507484
1700507485
千万不要“望文生义”，想当然地认为时间的增加和迭代次数成正比。具体的消耗时间需要通过实际的测量得到，这种方法更为准确。在其他算法场合下，可以用更大的N来尝试，例如1000、5000、10000、50000……这样的序列。对这些点的测量会给那些位于这些点之间的未测量的N的场景提供一个参考刻度。
1700507486
1700507487
结论2：如果可能，尽量测出这个极限的位置
1700507488
1700507489
也就是说，在合理的时间成本范围内尽量测出最后不再下降的单次试探时间。例如，连续2次增加N，都发现单次试探时间不再有明显下降，即可考虑给出这样的结论：可以作为更大的N出现时所花费时间的评估基础。
1700507490
1700507491
如果要在一个庞大的分布式集群里对未知节点上的某一条数据进行查找，在没有索引的情况下，使用的同样是典型的穷举法。别以为所有的查找场景情况下都会有索引，索引的建立和维护是有成本的，无论是OLAP系统，还是OLTP系统，对索引的使用都是比较谨慎的。
1700507492
1700507493
再如，在没有任何提示的情况下破解一个密码也是典型的穷举法使用场景——必须一个一个试过，才会知道这个密码是否与正确的密码吻合。
1700507494
1700507495
穷举法适用于数据量小、硬件极为丰富或信息预处理不充分的场景。要事先根据经验或实际的时间消耗测算来预估破解的总时长，以判断是否可以使用穷举法。
1700507496
1700507497
1700507498
1700507499
1700507500
数据科学家养成手册 [:1700503581]
1700507501
数据科学家养成手册 11.4 分治法——化繁为简
1700507502
1700507503
分治法的应用在生产中更为普及，而且这种思路可以说同样是浑然天成——也是人类自己处理复杂问题的逻辑。人类在碰到一个庞大而复杂的问题时同样会想：这个问题可不可以分解成多个简单一些的小问题？每个问题获解了，整体就获解了（如图11-10所示）。
1700507504
1700507505
1700507506
1700507507
1700507508
图11-10 问题分解
1700507509