第一章、 算法简介
一些常见的大O运行时间
》 O(log n)，也叫对数时间，这样的算法包括二分查找。
》 O(n)，也叫线性时间，这样的算法包括简单查找。
》 O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
》 O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
》 O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
小结
》 二分查找的速度比简单查找快得多。
》 O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
》 算法运行时间并不以秒为单位。
》 算法运行时间是从其增速的角度度量的。
》 算法运行时间用大O表示法表示。
第二章、选择排序
总结
计算机内存犹如一大堆抽屉。
需要存储多个元素时，可使用数组或链表。
数组的元素都在一起。
链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中，所有元素的类型都必须相同(都为int、double等)。
第三章、 递归、栈
关于递归
我怀着激动的心情编写本章，因为它介绍的是递归——一种优雅的问题解决方法。递归是我 最喜欢的主题之一，它将人分成三个截然不同的阵营:恨它的、爱它的以及恨了几年后又爱上它 的。我本人属于第三个阵营 --- 作者
计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。下面是一个 简单的函数。
def greet(name):
print( "hello, " + name + "!" greet2(name) )
print( "getting ready to say bye..." bye() )
这个函数问候用户，再调用另外两个函数。这两个函数的代码如下。
def greet2(name):
print( "how are you, " + name + "?")
def bye():
print ("ok bye!")
现在你又回到了函数
greet。由于没有别的事情要做，你就从函数greet返回。这个栈用于存储多个函数的变量，被称为调用栈。
递归调用栈
递归函数也使用调用栈!来看看递归函数factorial的调用栈。factorial(5)写作5!，其
定义如下:5! = 5 * 4 * 3 * 2 * 1。同理，factorial(3)为3 * 2 * 1。下面是计算阶乘的递归函数。
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
下面来详细分析调用fact(3)时调用栈是如何变化的。别忘了，栈顶的方框指出了当前执行 到了什么地方。
使用栈虽然很方便，但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。
重新编写代码，转而使用循环。
使用尾递归。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言
都支持尾递归。
小结
递归指的是调用自己的函数。
每个递归函数都有两个条件:基线条件和递归条件（递归用巧劲）
栈有两种操作:压入和弹出。
所有函数调用都进入调用栈。
调用栈可能很长，这将占用大量的内存。
递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。
网友评论