技术文档时间复杂度分析
时间复杂度分析
算法
内容
时间复杂度分析
什么是大O
这里的大O是指什么呢，说到时间复杂度，大家都知道O(n)，O(n^2)，却说不清什么是大O。
- 最坏情况
- 算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
- 一般情况
- 面试中说的算法的时间复杂度是多少指的都是一般情况。==但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。== 拿排序算法举例： 插入排序的时间复杂度我们都说是O(n^2)，同理再看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)。 但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。
数据规模差异
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶
O(logn)中的log是以什么为底
忽略底数,看图可知常数项系数可以忽略
递归的时间复杂度
递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。
例：求x的n次方
迭代 O(n)
int function1(int x, int n) {
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) {
result = result * x;
}
return result;
}
递归O(n)
int function2(int x, int n) {
if (n == 0) {
return 1; // return 1 同样是因为0次方是等于1的
}
return function2(x, n - 1) * x;
}
每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。
int function3(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n % 2 == 1) {//n是奇数
return function3(x, n / 2) * function3(x, n / 2)*x;
}
return function3(x, n / 2) * function3(x, n / 2);//n是偶数
}
我们来分析一下，首先看递归了多少次呢，可以把递归抽象出一棵满二叉树。刚刚同学写的这个算法，可以用一棵满二叉树来表示（为了方便表示，选择n为偶数16），如图：
这棵满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现。
这里每一层每一个节点都使用了，所以时间复杂度还是O(n)
递归O(n)
int function4(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
if (n % 2 == 1) {
return t * t * x;
}
return t * t;
}
每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的O(logn)。