“算法和算法分析”的版本间的差异

来自软件实验室
跳转至: 导航搜索
1.4.3 算法效率的度量
1.4.3 算法效率的度量
第7行: 第7行:
 
=== 计算方法 ===
 
=== 计算方法 ===
 
1.事后统计的方法
 
1.事后统计的方法
 +
 
2.事前分析估算的方法
 
2.事前分析估算的方法
 
=== 一个计算方法——大O计法 ===
 
=== 一个计算方法——大O计法 ===
 
1.常量阶O(1)
 
1.常量阶O(1)
 
eg:
 
eg:
* int sum=0,n=100;/*执行一次*/
+
  int sum=0,n=100;/*执行一次*/
* sum=(1+n)*n/2;/*执行一次*/
+
  sum=(1+n)*n/2;/*执行一次*/
* printf("%d",sum);/*执行一次*/
+
  printf("%d",sum);/*执行一次*/
 
解:运行次数函数f(n)=3,空间复杂度为O(1)
 
解:运行次数函数f(n)=3,空间复杂度为O(1)
 
另:
 
另:
* int sum=0,n=100;/*执行一次*/
+
  int sum=0,n=100;/*执行一次*/
* sum=(1+n)*n/2;/*执行一次*/
+
  sum=(1+n)*n/2;/*执行一次*/
* printf("%d",sum);/*第1次执行*/
+
  printf("%d",sum);/*第1次执行*/
* printf("%d",sum);/*第2次执行*/
+
  printf("%d",sum);/*第2次执行*/
* printf("%d",sum);/*第3次执行*/
+
  printf("%d",sum);/*第3次执行*/
* printf("%d",sum);/*第4次执行*/
+
  printf("%d",sum);/*第4次执行*/
* printf("%d",sum);/*第5次执行*/
+
  printf("%d",sum);/*第5次执行*/
* printf("%d",sum);/*第6次执行*/
+
  printf("%d",sum);/*第6次执行*/
 
解:运行次数函数f(n)=8,但是空间复杂度仍然为O(1)
 
解:运行次数函数f(n)=8,但是空间复杂度仍然为O(1)
  
第58行: 第59行:
 
     while (i<=n)
 
     while (i<=n)
 
       i=i*2; ②
 
       i=i*2; ②
解: 语句1的频度是1,   
+
解: 语句1的频度是1,  
 +
   
 
           设语句2的频度是f(n),  则:2^f(n)<=n;f(n)<=log2n     
 
           设语句2的频度是f(n),  则:2^f(n)<=n;f(n)<=log2n     
 +
 
           取最大值f(n)=log2n,
 
           取最大值f(n)=log2n,
 +
 
           T(n)=O(log2n )
 
           T(n)=O(log2n )
  

2016年4月10日 (日) 21:41的版本

1.4.1 算法

1.4.2 算法设计的要求

1.4.3 算法效率的度量

算法的时间复杂度

一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) T(n)=O(f(n))

计算方法

1.事后统计的方法

2.事前分析估算的方法

一个计算方法——大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).

建议参考博客:[1]

1.4.4 算法的存储空间需求