关于算法分析的基础问题

Question

用于丈量算法时间复杂度的O(n)、O(1)等是怎么算出来的，比如后缀计算表达式就是O(n)，怎么算的。。

Answer 1

简单来说，如果一个算法，按照数据输入量的增长，它的运算时间的增长是线性的，那么就是O(n)
比如说，线性搜索，后缀表达式的计算因为只要遍历一次表达式，并且无需回溯，那么也是O(n)。而二分搜索，很显然，需要搜索的次数肯定少于log2(n)，所以就是O(logn)
如果一个算法，运行时间和数据量无关，那么就是O(1)。比如说判断链表是否为空，不管链表有多长，都只需要读取第一个元素，所以是O(1)。

如果你愿意分析代码，那么看下，如果是单个循环，循环结束变量和数据长度相关，那么就是O(n)。如果是二重循环，并且循环结束变量都和数据长度相关，那么就是O(n^2)。如果你不想分析代码，那么就用不同的数据量测试，并且得到运行时间。并且在纸上描点，如果基本看上去是线性的，那么就是O(n)，如果是水平直线（没变化），就是O(1)，如果是抛物线，就是O(n^2)，如果是幂数（看上去越来越缓），就是O(logn)，如果是双曲线（越发接近一个常数），就是O(1/n)，等等。