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

时间复杂度是衡量一个算法好坏的重要标准，拿排序算法来说，同样是排序可以选择时间复杂度为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)
• 扩充：指数级别的时间复杂度是相当恐怖的，很容易导致堆栈溢出，所以对于上述问题我们可以采用记忆型递归(空间换时间) 或 递推公式求解