【数据结构与算法】如何分析、统计算法的执行效率和资源消耗

luoyjx · 2018-10-30 21:00 · 79次阅读

为什么需要复杂度分析

  • 测试结果非常依赖测试环境
  • 测试结果受数据规模影响很大

大 O 时间复杂度表示法

表示 标识代码执行时间随数据规模增长的变化趋势

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

时间复杂度分析

只关注循环执行次数最多的一段代码

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

加法法则,总复杂度等于量级最大的那段代码的复杂度

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

乘法法则,嵌套代码的复杂度等于嵌套内外复杂度的乘积

int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

几种常见的时间复杂度

  • 常量阶 O(1)
  • 线性阶 O(n)
  • 对数阶 O(logn)
  • 线性对数阶 O(nlogn)
  • 平方阶 O(n²)
  • 立方阶 O(n³)
  • k 次方阶 O(nk次方)
  • 指数阶 O(2n次方)
  • 阶乘阶 O(n!)

空间复杂度分析

标识算法的存储空间与数据规模之间的增长关系

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}
收藏

暂无评论

登录后可以进行评论。没有账号?马上注册