算法 基础
- 二分查找的速度比简单查找快得多.
- O(log n)比O(n)快. 需要搜索的元素越多, 前者比后者就快得越多.
- 算法运行时间并不以秒为单位, 而是主要操作执行次数.
- 算法运行时间是从其增速的角度度量的.
- 算法运行时间用大O表示法表示.
常见的大O运行时间
- O(log n)，也叫对数时间，这样的算法包括二分查找。
- O(n)，也叫线性时间，这样的算法包括简单查找。
- O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
- O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
- O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。旅行商问题
数组和链表
数组, 内存地址相连, 可以使用下标直接访问指定内存. 索引快(O(1)), 增删慢(O(n))
尾递归
每个递归函数都有两个条件:基线条件(不再调用自己)和递归条件(调用自己)。
递归是自己调用自己, 递归中调用自己是最后一个语句, 并且调用自己的返回值不做后续
操作.
尾递归可以很方便的优化成循环(python, java 为了维持异常栈, 所以不会对此优化)
通用算法
分而治之, divide and conquer，D&C, 一种著名的递归式问题解决方法
Reference