数据结构与算法分析学习笔记(1)

O（logN）<O(N)

关于递归算法，

long int
Fib（int N）
 {
    if（N《=1）
      return 1；
    else
        return Fib（N-1）+Fib （N-2）；
}

Fib函数对于N>=2时，运行时间 T（N）=T（N-1）+T（N-2）

Fib(N)<(5/3)ⁿ，可见这个程序是运行时间是以指数的速度增长；

这个程序之所以运行缓慢，是由于存在大量多余的工作要完成，在Fib（N-1）+Fib（N-2）中，第一次调用Fib（N-1）实际上计算了FIb（N-2），这个信息被抛弃而在第二次调用时又重新计算了一遍，抛弃的信息量递归的合起来并导致巨大的运行时间。

一段分析代码的逻辑

int MaxSubsequence(const int A[].int N)
{
    int ThisSum MaxSum ,i,j,k;
    MaxSum=0;
    for(i=0;i<N;i++)
       for(j=i;j<N;j++)
           {
               ThisSum=0;
               for(k=i;k<=j;k++)
                   ThisSum+=A[k];
               if(ThisSum>MaxSum)
                   MaxSum=ThisSum;
            }
       return MaxSum;
}

运行时间完全取决于第三重for循环的执行语句；

第一个for循环执行为 N次

第二个for循环执行为N-i次

第三个for循环为 j-i+1次

因此执行次数为：∑_i=0^N-1*∑_j=i^N-1*∑_k=i ^j*f(1)

根据公式从内向外求值：第一个∑为∑=j-i+1；

第二个∑为∑=∑(j-i+1)=(N-i+1)*(N-i)/2

第三个∑为∑=∑（N-i+1）*(N-i)/2=（N³+3N²+2N）/6

因此T（N）=O（N³）

----------------------------------------------------------------------------------------------------------------------------------------------

分析算法最混乱的方面集中在对数上面。某些分治算法将以O（NlogN）时间运行。

对数常出现的规律概括一下一般规则：如果一个算法用常数时间O（1）将问题的大小消减为其一部分（1/2）,那么该算法就是O（logN），另一方面，如果使用常数时间只把问题减少一个常数(如将问题减少1)，那么这种算法就是

O（N）的。

典型例子：二分查找；

典型例子之欧几里得算法

 1 unsigned  int Gcd(unsigned  int M,unsigned int N)
 2 {
 3     unsigned int REM;
 4     if(N!=0)
 5        {
 6            REM=M%N;
 7            M=N;
 8            N=REM;
 9        }
10      return N;
11 }

估计Gcd算法的整个运行时间依赖于确定余数序列究竟有多长，在一次迭代中余数并不是按照一个常数因子递减，然而可以证明，在两次迭代以后，余数做多是原始值的一半，从而证明了至多2logN=O（logN）。

定理：如果M>N,则M mod N <M/2

典型例子之幂运算

比较容易想得到的算法是Xⁿ是n-1次自乘，这里有个递归算法会更好；利用偶数情况Xⁿ=X^n/2*X^n/2，奇数情况之下，Xn=X^（n-1）/2*X^（n-1）/2*X

 1 long int Pow(long int M, unsigned int N)
 2 {
 3    if(N==0)
 4      return 1;
 5   if(1==N)
 6      return M;
 7   if(IsEven)
 8     return  Pow(M*M ,N/2)；
 9   else
10     return Pow（M*M，N/2）*M；
11 }

算法分析，显然所需要的乘法次数最多是2logN，因为把问题分半最多需要两次乘法。
第10行可以改写为如下而不影响其正确性：

1 return Pow （M，n-1）*M；

但是第8行改成如下就是不对的；

return Pow（Pow（M，2），n/2）；//第一种改写，当n是2时，调用pow时，有一个是以2为参数，此时程序进入死循环
return Pow （Pow(M,n/2),2);//第二种改写，当n是2时，调用pow时，有一个是以2为参数，此时程序进入死循环
return Pow（M，n/2）*Pow（M，n/2）；//第三种改写，此时两次调用pow，运行时间不再是O（logN）

证明，任何通过使用比较来进行排序的算法在最坏情况之下只需要Ω（NLogN）次比较；

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

数据结构与算法分析 学习笔记(1)

数据结构与算法分析学习笔记(1)