【数据结构实战C++】4 算法复杂度概念

【数据结构实战C++】4 算法复杂度概念

作者 CodeAllen ，转载请注明出处

效率是工程中最关注的算法特性

算法效率的量度的几个方法

事后统计法
-比较不同算法对同一组输入数据的运行处理时间
-缺陷

• 为了获得不同算法的运行时间必须编写相应程序
• 运行时间严重依赖硬件以及运行时的环境因素
• 算法的测试数据的选取很困难

事前分析估算
-依据统计的方法对算法效率进行估计
-影响算法效率的主要因素

• 1，算法采用的策略和方法
• 2，问题的输入规模
• 3，编译器所产生的代码
• 4，计算机的执行速度

算法效率的简单估计一

算法效率的简单估计二

算法效率的简单估计三

程序效率估算

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int func(int a[], int len) // ==> (n*n + 2)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int ret = 0;      // 1
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    for(int i=0; i<len; i++)     
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        for(int j=0; j<len; j++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  ret += a[i] * a[j];  // n * n
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    return ret;                  // 1
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int array[] = {1, 2, 3, 4, 5};
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

          cout << func(array, 5) << endl;
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

上述程序关键部分的操作数量是n*n
三种求和算法中关键部分操作数量分别是2n, n ,1

不同算法操作数量的对比

算法操作数量对比一

算法操作数量对比二

算法操作数量对比三

小结
算法度量方法有 事后统计法和事前分析估算法
事后统计法不容易准确度量算法的效率
事前分析估算法通过操作数量度量算法效率
判断一个算法效率时只关注最高阶项就能得到结论

算法随着问题规模n的增大，会越来越优越于另一个算法，或者越来越差于另一个算法

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/89224648