问题描述

关于算法分析的基础问题

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

解决方案

简单来说，如果一个算法，按照数据输入量的增长，它的运算时间的增长是线性的，那么就是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)，等等。

解决方案二：

比如

 if(n>1){    //这里的判断的时间复杂度为 O(1)
    for(int i=0;i<n;i++){
           //这里做了从0到n的循环，那时间复杂度为O(n)
        }
    for(int i=0;i<n;i++){
               for(int i=0;i<n;i++){
                     //这里做了从0到n的两次循环，那时间复杂度为O(n*n)
                }
        }
 }

解决方案三：

表示看不懂，觉得是数学专业出身的一样。看着自己像一个小白。顶！大神！学习！

解决方案四：

关于复杂度（分为时间复杂度和空间复杂度）。算法导论的第一章就做了介绍，任何数据结构的书也都会介绍的～
楼上第一位回答的非常精辟！

解决方案五：

算法分析基础
【算法设计与分析基础】背包问题
（二） 算法分析基础