算法-复杂度

大O表示法 

评估算法性能，主要评估的问题是输入规模n与元素的访问次数f（n）的关系

O（g（n）），g（n）是这个算法的复杂度上界。

例如O（n^2），算法的最大消耗就是n^2，因为评估是往往把低阶项和常用省略。

所谓复杂度就是看循环内的语句执行次数的量级。

理解对数

2^4 = 16

以2为底数，增长10次就到达了1024

n^2就是整体取值的趋势

4 = log2^16，表示16以2为底数减少，减少4次为1

也可表示当指数以log2^n的速度增长时，那么对数整体以n^2的速度增长

从计算的角度理解复杂度

如果计算机一秒能处理O(n)的运算10的八次方次，那么一秒能处理O(n^2)的运算就为10的四次方次，一秒能处理O(n^3)的运算为500次。CPU处理的运算的次数是一样的，但是解决的问题的多少是不同的，能解决O(n)类型的问题10的八次方个的话，只能解决O(n^3)类型的问题500个，如果能将O(n^3)的问题转换为O(n)类型的问题，那么问题的解决效率将大大提高。

问题的复杂度高，意味着处理一个问题将花费的时间长，单位时间内计算的单位就很小，也就是计算的很慢。

 相同的问题，如果复杂度是n，意味着有n的数量级次计算，如果是n^3，意味着有n^3数量级次计算。

递归形式算法的性能分析

 求n的阶乘

static int f1(int n){
    if(n==1)
        return 1;
    return n*f1(n-1);
}

乘n是常数阶运算O（1），T（n）=O（1）+T（n-1），每次运算都是O（1），一共有n次，就是n*O（1），得O（n）。

斐波那契

public static int f1(int n){
        if(n==1 || n==2) return 1;
        return f1(n-1) + f1(n-2);
    }

T（n） = T（n-1）+T（n-2）+O（1）

            约等于  2*T（n-1）+O（1）= 2*（T（n-2）+T（n-3）+O（1））+O（1）

            约等于 2*2*T（n-2）+3O（1）

            减多少次就乘多少个2

             最后得2^n