算法和算法分析

1.4.3 算法效率的度量

算法的时间复杂度

一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)

T(n)=O(f(n))

【补充】

称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为

界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。

计算方法

1.事后统计的方法

2.事前分析估算的方法

一个计算方法——大O计法

什么是大O计法

【有待商讨交流】

大O计法是算法的时间复杂度表达公式。简单地说，大O计法可以告诉你一个算法耗费的时间长度同算法所处理的数据量大小的关系。大O计法只是一个概念性的或定性的记号，不能通过它来真正计算一个算法所耗费的精确时长。

常见类型

1.常量阶O(1) eg:

  int sum=0,n=100;/*执行一次*/
  sum=(1+n)*n/2;/*执行一次*/
  printf("%d",sum);/*执行一次*/

解:运行次数函数f(n)=3,空间复杂度为O(1) 另:

  int sum=0,n=100;/*执行一次*/
  sum=(1+n)*n/2;/*执行一次*/
  printf("%d",sum);/*第1次执行*/
  printf("%d",sum);/*第2次执行*/
  printf("%d",sum);/*第3次执行*/
  printf("%d",sum);/*第4次执行*/
  printf("%d",sum);/*第5次执行*/
  printf("%d",sum);/*第6次执行*/

解:运行次数函数f(n)=8,但是空间复杂度仍然为O(1)

2.线性阶O(n) eg:

   a=0;
   b=1;                      ①
   for
(i=1;i<=n;i++)          ②
   {  
      s=a+b;　　　　③
      b=a;　　　　　④  
      a=s;　　　　　⑤
   }

解：语句1的频度：2,

          语句2的频度：n,    
         语句3的频度： n-1,        
         语句4的频度：n-1,    
         语句5的频度：n-1,                                  
         T(n)=2+n+3(n-1)=4n-1=O(n).

3.平方阶O(n^2) eg:

     交换i和j的内容
    sum=0；                 （一次）
    for(i=1;i<=n;i++)       （n次 ）
       for(j=1;j<=n;j++)
（n^2次 ）
        sum++；       （n^2次 ）

解：T(n)=2n^2+n+1 =O(n^2)

4.对数阶O(logn) eg:

    i=1;       ①
    while (i<=n)
     i=i*2; ②

解： 语句1的频度是1,

         设语句2的频度是f(n),   则：2^f(n)<=n;f(n)<=log2n    

         取最大值f(n)=log2n,

         T(n)=O(log2n )

eg:

  int count=1;
  while(count<n)
  count=count*2;

解:2*x=n,得到x=log2(n),所以时间复杂度为O(logn)。

5.指数阶O(2^n)

   for(i=0;i<n;i++)
   {  
      for(j=0;j<i;j++)  
      {
         for(k=0;k<j;k++)
            x=x+2;  
      }
   }

解：当i=m,

j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

常见的时间复杂度

O(1) < O(lgn) < O(n) < O(nlgn) < O(n2)< O(n3)<O(2n) < O(n!) < O(nn)

最坏情况与平均情况

比如n个顺序存储元素进行排序，a[0]做“哨兵”（即a[0]不存数据，而是用作辅存空间使用）的情况

1 直接插入排序：比较次数 最少n-1次；最多(n-1)(n+2)/2

                           移动次数 最少0； 最多(n-1)(n+4)/2

                          使用一个辅助存储空间，是稳定的排序；

2 折半插入排序：比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），

               移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
               使用一个辅助存储空间，是稳定的排序；

3 冒泡排序： 比较最少为：n-1次，最多时间复杂度表示为o(n2);

                     移动次数最少为0，最多时间复杂度表示为O(n2);

                       使用一个辅存空间，是稳定的排序；

4 简单选择排序： 比较次数没有多少之分，均是n(n-1)/2;

                           移动次数最少为0，最多为3(n-1);

                            使用一个辅存空间，是稳定的排序；

5 快速排序：比较和移动次数最少时间复杂度表示为O(n*log2n);

                   比较和移动次数最多的时间复杂度表示为O(n2);

                   使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；

6 堆排序： 比较和移动次数没有好坏之分，都是O(n*log2n);

                 使用一个辅存空间，是不稳定的排序；

7 2-路归并排序：比较和移动次数没有好坏之分，都是O(n*log2n);

                   需要n个辅助存储空间，是稳定的排序；

参考资料

建议参考博客:[1]

1.4.4 算法的存储空间需求

定义

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

计算公式

S(n)= O(f(n))

参考资料

[2]