Unresolved Problems List

1. 平均复杂度和分摊复杂度的概念

2. 输入敏感：一个算法对于输入实例的最好和最坏情况性能差别巨大

3. Fibonacci数列与黄金分割比例的关系：

让我们首先从一个数列开始，它的前面几个数是：1、1、2、3、5、8、13、21、34、55、89、144…..这个数列的名字叫做"菲波那契数列"，这些数被称为"菲波那契数"。特点是即除前两个数（数值为1）之外，每个数都是它前面两个数之和。
菲波那契数列与黄金分割有什么关系呢？经研究发现，相邻两个菲波那契数的比值是随序号的增加而逐渐趋于黄金分割比的。即f(n-1)/f(n)-→0.618…。由于菲波那契数都是整数，两个整数相除之商是有理数，所以只是逐渐逼近黄金分割比这个无理数。但是当我们继续计算出后面更大的菲波那契数时，就会发现相邻两数之比确实是非常接近黄金分割比的。

4. 有序向量查找的三个版本：
   1.分支判断三种转向，当区间宽度等于0时停止循环。转向需要比较的次数分别为一次和两次。因此，需要选择合适的Mid来优化。一般有二分查找和Fibonacci查找，且后者更优。
   2.分支判断两种转向，比较稳定。当区间宽度等于1时停止循环。缺点是不论好坏，都得等到最后才能进行判断是否相等
   3.分支判断两种转向，当区间宽度等于0时停止循环。最后是return lo--

5. 起泡排序的三个版本：
   1.不做任何改进的普通版本，最好O（n）,最坏O（n*n）

6. 设置Flag sorted
   2.记录最后未进行Swap的位置（意味着这位置好后面的序列是有序的）