简介
执行效率是算法一个非常重要的考量指标。衡量编算法代码的执行效率:时间、空间复杂度。
大 O 复杂度表示法
1 int cal(int n) {
2 int sum=0;
3 int i=1;
4 for(;i<=n;++i){
5 sum=sum+i;
6 }
7 return sum;
8 }
假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，这段代码的总执行时 间是多少呢?
第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+2)*unit_time。可以看出来， 所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i){
j = 1;
for (; j <= n; ++j){
sum = sum + i*j
}
}
}
执行时间为T(n) = (2 *n * n + 2n + 3)*unit_time
但是通过这两段代码执行时间的推导过程，我们可以得到 一个非常重要的规律，那就是，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
T(n) 我们已经讲过了，它表示代码执行的时间;n 表示数 据规模的大小;f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。 公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左 右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表 示刚讲的那两段代码的时间复杂度，就可以记为:T(n) = O(n); T(n) = O(n^2)。
时间复杂度分析
- 只关注循环次数最多的一次代码
- 加法法则: 总复杂度等于量级最大的那段代码的复杂度。(如顺序执行的代码,所以是一个常量的执行时间，跟 n 的规模无关。)
- 乘法法则: 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几种常见时间复杂度实例分析
- 常量阶: O(1)
- 对数阶: O(logn)
- 线性阶: O(n)
- 线性对数阶: O(nlogn)
- 平方阶:
O(n^2) 、 O(n^3) ....
- 指数阶: O(2^n)
- 阶乘阶: O(n!)
其实就是统计执行次数
实际举例:
1). 常量阶: O(1)
顺序执行代码的复杂度就是O(1),
O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一 行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1)，而不是 O(3)。
2). O(logn)、O(nlogn)
对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。
i=1;
while(i <= n) {
i=i*2;
}
1*2*2*2*2..直到>n停止,因此需要 2^p > n , p为执行次数, 可得知p的值为以2为底n的对数, 即p = log2 n
实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度 都记为 O(logn)。为什么呢?
如果你理解了我前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则 吗?如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间 复杂度都是 O(nlogn)。