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

来自软件实验室
跳转至: 导航搜索
(创建页面,内容为“== 1.4.1 算法 == == 1.4.2 算法设计的要求 == == 1.4.3 算法效率的度量== == 1.4.4 算法的存储空间需求 ==”)
 
1.4.3 算法效率的度量
第2行: 第2行:
 
== 1.4.2 算法设计的要求 ==
 
== 1.4.2 算法设计的要求 ==
 
== 1.4.3  算法效率的度量==
 
== 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).
 +
 +
建议参考博客:[http://blog.csdn.net/firefly_2002/article/details/8008987]
 +
 
== 1.4.4 算法的存储空间需求 ==
 
== 1.4.4 算法的存储空间需求 ==

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

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 算法的存储空间需求