关于android:算法的时间复杂度

算法的工夫与空间复杂度

预先分析法

毛病：不同的数据规模，不同的机器下算法运行的工夫不同，无奈做到计算运行工夫

事先分析法

大 O 工夫复杂度

渐进工夫复杂度 随着 n 的增长，程序运行工夫追随 n 变动的趋势

几个准则

去掉常数项

2(n^2) =n^2

一段代码取工夫复杂度最高的

test(n) {
  // 工夫复杂度 n^3
 for(int i = 0; i < n ; i++){for(int i = 0; i < n ; i++){for(int i = 0; i < n ; i++){print(n);
     }
   }
 }
 // 工夫复杂度 n^2
 for(int i = 0; i < n ; i++){for(int i = 0; i < n ; i++){print(n);
   }
 }
 // 工夫复杂度 n
 for(int i = 0; i < n ; i++){print(n);
 }
}

这段代码的工夫复杂度为 n^3+n^2+n

当 n 足够大时，n^2 和 n 与 n^3 相比太小，能够忽略不计

常见复杂度

o(1)

i = i + 1;

o(n)

test(n){for(int i = 0 ;i < n;i++){print(i);
  }
}

o(n^2)

test(n){for(int i = 0 ;i < n;i++){print(i);
    for(int j = 0 ;j < n;j++){print(i);
    }
  }
}

o(log2n)

PS: 如果 ax =N（a>0，且 a≠1），那么数 x 叫做以 a 为底 N 的对数，记作 x =logaN，读作以 a 为底 N 的，其中 a 叫做对数的底数，N 叫做真数。

test(n) {
  int i = 1;
  while (i <= n) {i = 2 * i;}
}

随着循环次数的减少，i 的值变动如下

依据对数函数的公式 2 的 i 次方等于 n,i 等于 log2n

最好状况工夫复杂度

数据比拟有序的状况的工夫复杂度

最坏状况工夫复杂度

数据齐全无序

空间复杂度

与 n 无关的代码空间复杂度能够疏忽

空间复杂度 O(n)

test(n) {
  // 在内存中开拓了一个长度为 n 的数组
  List array  =  List(n);
  print(array.length);
}

本文由博客群发一文多发等经营工具平台 OpenWrite 公布