数据结构-算法分析

算法是什么

答案顾名思义，有着一些指示用来解决问题的就是算法。 程序只是用来将算法表达出来。

如何量度算法的表现?

四点： 1. 程序代码的长度 2. 程序的维护工作 3. 容量空间的要求 4. 运行时间 其方法：时间复杂度) Time of Complexity（时间复杂度）： 我们运用到4中非对称表达式：

1\. Big-O —>(T(n) = O(f(n))
T（n） <= c*f(n) —>’Bounded above by’ (渐进上界)
2\. Big-Omega —>(T(n) = Omega（f(n)）)
T(n) >= c *f(n) —>”bounded below by” (渐进下界)
3\. Big-Theta
T(n) = c *f(n) —>”bounded below and above by”
4\. Big-littleo —-> T（n）< c f(n)
T(n)/p(n) ->0 as n —>无限大 （严格下界）

通常Big-O在数据结构中用的最多，因为我们需要量度算法的下界，也就是worst case, Big-Omega较少用到，毕竟很难量度最好表现 数据结构的一些会用到的公式（Useful rules of data structure）:

Rule 1: 加法法则（rule of sum）
 T1(n) + T2(n) = O(max(T1(n), T2(n)))
Rule 2: 乘法法则（rule of product）
 T1(n) * T2(n) = O(T1(n) * T2(n))
Rule 3: log^k n = O(n) 且 在任何k值的情况下（For any constant k） –> log的增长率十分慢（log grows very slowly）

一般情况下，时间复杂度是由许多部分组成，只需要找出最大的部分 除去其他部分（包括乘法因子） 普遍的复杂度(从小到大)：

O(1) , O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n), O(n!)

前面是介绍一些数据结构的定义和数学， 现在下面介绍的是正式的对算法的分析： 算法中， 既定的规则：

1.一些基本的语句(assign, read or write or +-/*==) 运行时间： constant O(1) 2. 循环语句一般看循环的次数

for(i = 0; i< n; i++){
        if(a == n-1){
            return 1;
        }
    }  --->运行时间：O（n）

3.. Nested loops(嵌套循环)所有循环的次数size相乘

for (i=1; i<n-1; i++)  --> O(n)
for (j=n; j>= i+1;  j--)  --> O(n)
if (A(j-1) > A(j)) then
temp = A(j-1);
A(j-1) = A(j);
A(j) = tmp;

总运行时间： O(n^2) 4.. If/else 决策算法 根据所测试的部分来决定该算法的时间复杂度， 不过条件是constant O(1)