Python算法教程学习笔记＿第一章

为什么要读这本书

  当我们在工作中使用算法时，通常都是希望能更有效地解决问题，使程序运行得更快，并且让解决方案更为简短．便实际情况如何呢？我们获得所需要的效率，速度和简洁性了吗？为什么人们在使用Python这种语言时依然要在乎这些事呢？选择这种语言对于追求高速度的人是一个好的开端吗？为什么不选择Ｃ或JAVA这样的语言呢？ 首先，可能是因为Python语言本身很讨人喜欢，以至于人们不想换别的语言，或者他们目前也没有更好的选择。但最为重要的可能还是第二点，即在这里，算法设计者们首先要担心的并不是常数级别的性能差异。即便相关程序完成任务所需要的时间是另一程序的两倍，甚至十倍但这样的速度可能依然是够快的，况且，那个较慢的程序（或语言）中可能恰好有某些我们所需要的特性，如它可能有更好的可读性，而调整和优化程序在很多时候会非常费幼，其代价是不容小视的。然而，无论选择什么语言，我们都得考虑一下程序自身的弹性问题。也就是说，如果我们将程序的输入量翻倍，会发生什么呢？程序运行时间会是之前的两倍？四倍？还是更多？或者即便增加那么一丁点的输入量也会导致程序运行时间的成倍增长？当您遇到的问题足够大的时候，这样的性能差异显然就不能再靠简单的语言选择或硬件选择来解决了，在面对一个“足够大”的问题（在某些情况下，当问题还没有特别大的时候，它就已经“足够大”了）时，我们能抑制运行时间增长的主要武器就只有一您猜对了一份扎实的算法设计功底了。

小实验

>>> count = 10**5
>>> nums= []
>>> for i in range(count):
...     nums.append(i)
...
>>> nums.reverse()

  这段代码并没有什么实际用处。只是把一堆数字添加到一个空list里，然后反转这个list。 在实际的情形当中，这些数字可能来自外部，你想要把这些数字反向加入你的list，也就是往前插入。是啊，为什么我们不直接在list前面插入呢？

>>> nums= []
>>> for i in range(count):
...     nums.insert(0,i)

  除非我们以前遇到过类似的情况，否则一定会觉得这段新代码看上去很不错．但如果您有机会试一试的话，就会发现其实速度反而是明显变慢了．至少在我的计算机上，第二段代码完成任务所需的时间大约是第一段的200倍．而且不仅是速度变慢了，其应对问题规模的性能弹性也更差了．

　这是一个拿线性增长和二次方增长相比较的例子．