美文网首页
1001_程序时间复杂度及拓展

1001_程序时间复杂度及拓展

作者: 掌灬纹 | 来源:发表于2020-04-14 21:01 被阅读0次

    时间复杂度是衡量一个算法好坏的重要标准,拿排序算法来说,同样是排序可以选择时间复杂度为O(n^2)的冒泡排序,还可以选择O(nlogn)的快排(或归并排序),这样比较就明显发现快排算法肯定是优于冒泡排序的(两者都不涉及空间占用)

    • 时间复杂度的分析是基本功,在算法竞赛中我们必须要依据题目给出的测试数据范围,来设计相应复杂度算法,这里就不在深入展开。在考研范围内我们要掌握的就是可以分析自己的伪码,还有题目中代码的复杂度

    下面举几个比较简单的时间复杂度分析例子

    • O(√n) 简单分析一下,跳出循环的条件是y^2级别的增长 | 增长到n 所以y^2<=n -》y<=√n
    int y = 0;
    while((y+1)*(y+1) <= n)
          y += 1;
    
    • (14 年统考真题) O(nlogn)
    count = 0;
    for(k=1;k<=n;k*=2)
      for(j=1;j<=n;j++)
        count++;
    
    • (17 年统考真题)
    int func(int n){
      int i = 0; sum = 0;
      while(sum < n) sum += ++i;
    }
    
    • 解析:解释一下17年的真题 虽然不难但还是比较容易算错的,其实这题考的不是时间复杂度的分析,而是阅读代码的能力(是否理解前缀++)下面将源码拆分一下时间复杂度便一眼看出 | 跳出循环的条件为累加级别的增长(1+2+3+..+t) < n;简单的求和等差数列求和公式可以知道是 t^2 级别的增长 即同第一题 O(√n) 拆分代码如下
    int func(int n){
      int i = 0; sum = 0;
      while(sum < n){
          i++;
          sum+=i;
      }
    }
    
    • 小结:总体来说时间复杂度分析是送分题,但还要在掌握分析方法的同时还要细心

    拓展:递归程序时间复杂度的分析

    • 引例:斐波那契数列;后项是前两项的和
      形如:1,1,2,3,5... f(1)=1,f(2)=1, f(n)=f(n-1)+f(n-2)
    • 递归程序 O(2^n)
    int Fibo(int n){
      if(n <= 0) return -1;
      if(n == 1 || n == 2)
          return 1;
      return Fibo(n-1) + Fibo(n-2);
    }
    
    • 分析:对于递归程序的分析,我们要理解它具体是如何调用的;如上述程序对于任何一个大于2的整数,程序都会深入调用计算 前两位,就如同一个二叉树一样 每次调用都会分成两部分,最终总次数就是(2^0 + 2^1 + 2^2 + .. + 2^(n-1)) 等比数列求和 2^n - 1 所以最终的时间复杂度 O(2^n)
    • 扩充:指数级别的时间复杂度是相当恐怖的,很容易导致堆栈溢出,所以对于上述问题我们可以采用记忆型递归(空间换时间)递推公式求解

    相关文章

      网友评论

          本文标题:1001_程序时间复杂度及拓展

          本文链接:https://www.haomeiwen.com/subject/ybkxvhtx.html