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)
1700507390
1700507391
这也是在熵最大的情况下查找的平均次数。需要强调的是，这是一种将场景简化为纯学术层面的讨论方式。在实际的算法编写过程中，数据在寄存器、内存、磁盘上的处理时间成本是非常悬殊的，所以这种讨论通常存在于学术层面，都是在理想条件下进行的讨论，这是它的局限性。不过，即使这样，也不能说它是错误的，因为它是一种被学术界广泛认可的、理论指导意义很高的度量方式，而且描述简洁方便。
1700507392
1700507393
在具体的生产中，还是建议分两步走。第一步，在刚刚所列举的纯模型层面去做一个规模性的估算，尽量避免比线性增加O(n)时间复杂度更高的情况出现。第二步，以生产场景中的处理规模与硬件设备做实测或等比缩放的实测。
1700507394
1700507395
1700507396
1700507397
1700507398
数据科学家养成手册 [:1700503580]
1700507399
数据科学家养成手册 11.3 穷举法——暴力破解
1700507400
1700507401
这种方式最原始、最笨重，但也最简单，千万不要觉得自己如果想到用这种方法去解决问题就万分羞赧，因为它同样是一种人与生俱来的解决问题的思维方式。
1700507402
1700507403
在少量数据的场合，以及硬件资源极为丰富的情况下，穷举法反而是最经济的办法，因为它消耗的资源是最廉价的。否则，要解决问题还需要进行一系列的建模、优化、测试、调整、论证、反复比对等过程，这种时间成本及在人工上的消耗很难忽略不计。
1700507404
1700507405
这种场景对于模型的解空间有限离散的情况最为合适。
1700507406
1700507407
经典的“八皇后问题”的求解（代码如下）就是穷举法，反正计算规模是非常小的——8的8次方，只要16777216次计算就可以完成，这对现代高速的计算机来说简直是“秒得”的结果。这种情况下，我在写程序时也会优先考虑直接穷举，因为我不确定在保证自己不出错的情况下进行优化，得出解的速度是不是更快。
1700507408
1700507409
def conflict(state, nextX): nextY=len(state) for i in range(nextY): if abs(state[i]-nextX)in(0, nextY-i): return True return Falsedef queens(num, state=()): for pos in range(num): if not conflict(state, pos): if len(state)==num-1: yield(pos, ) else: for result in queens(num, state+(pos,)): yield(pos, )+ result def prettyprint(solution): def line(pos, length=len(solution)): return ‘. ‘ *(pos)+ ‘X ‘ + ‘. ‘*(length-pos-1) for pos in solution: print line(pos) if __name__==“__main__”: i=0 for solution in queens(8): i+=1 print ‘solution:’ + str(i)+ ‘\n’ prettyprint(solution)