根据定义，时间复杂度指输入数据大小为 N 时，算法运行所需花费的时间；
体现的是计算操作随数据大小 N 变化时的变化情况，假设算法运行总共需要「 1 次操作」、「 100 次操作」，此两情况的时间复杂度都为常数级
O(1)；需要「 N 次操作」、「 100N 次操作」的时间复杂度都为O(N)；
符号表示
-
根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况，分别使用 O, Θ, Ω 三种符号表示；
-
以下借助一个查找算法的示例题目帮助理解；
// 线性查找，即遍历整个数组，遇到 7 则返回 true function findSeven(nums) { for (let num of nums) { if (num === 7) return true; } return false; }- 最佳情况
Ω(1)： nums = [7, a, b, c, …] ，即当数组首个数字为 7 时，无论 nums 有多少元素，线性查找的循环次数都为 1 次； - 最差情况
O(N)： nums = [a, b, c, …] 且 nums 中所有数字都不为 7 ，此时线性查找会遍历整个数组，循环 N 次（大 O 是最常使用的时间复杂度评价渐进符号，下文示例与本 LeetBook 题目解析皆使用 O）； - 平均情况
Θ： 需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等；
- 最佳情况
复杂度的计算方法
复杂度与具体的常系数无关：
- 例如 O(n) 和 O(2n) 表示的是同样的复杂度；
- O(2n) 等于 O(n+n) ，也等于 O(n) + O(n)；
- 也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n) ，其复杂度是一致的；
多项式级的复杂度相加的时候，选择高者作为结果：
- 例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度；
- O(n²)+O(n) = O(n²+n) 随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的；
- 因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了；
常见种类
常数 O(1)
运行次数与 N 大小呈常数关系，即不随输入数据大小 N 的变化而变化
function Func(void) {
for (var i = 0; i < 100; i++) {
printf("hello"); // 执行一百次，也是常量级，记为 O(1)
}
}
线性 O(N)
循环运行次数与 N 大小呈线性关系，时间复杂度为
O(N)
function Func(int n) {
for (var i = 0; i < n; i++) {
printf("hello");
}
}
平方 O(N^2)
两层循环相互独立，都与 N 呈线性关系，因此总体与 N 呈平方关系，时间复杂度为
O(N^2)
function algorithm(N) {
let count = 0;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
count++;
}
}
return count;
}
指数 O(2^N)
生物学科中的 “细胞分裂” 即是指数级增长；初始状态为 1 个细胞，分裂一轮后为 2 个，分裂两轮后为 4 个，……，分裂 N 轮后有 2^N 个细胞；
.jpg "指数 O(2^N)")
function algorithm(N) {
if (N <= 0) return 1;
let count_1 = algorithm(N - 1);
let count_2 = algorithm(N - 1);
return count_1 + count_2;
}
阶乘 O(N!)
阶乘阶对应数学上常见的 “全排列”；
即给定 N 个互不重复的元素，求其所有可能的排列方案数量为：
N × (N−1) × (N−2) × ⋯ × 2 × 1 = N!
function algorithm(N) {
if (N <= 0) return 1;
let count = 0;
for (let i = 0; i < N; i++) {
count += algorithm(N - 1);
}
return count;
}
对数 O(logN)
对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况”；
对数阶常出现于「二分法」、「分治」等算法中，体现着 “一分为二” 或 “一分为多” 的算法思想；
.jpg "对数 O(logN)")
function Func(n) {
// x 为循环次数，2^x = n，即 x = log2^n
// 不管 log 的底数是几，是 e 也好，是 10 也罢，统统记为 logn
for (var i = 1; i < n; i = i * 2) {
console.log(i);
}
}
线性对数 O(NlogN)
两层循环相互独立，第一层和第二层时间复杂度分别为 O(logN) 和 O(N) ，则总体时间复杂度为
O(NlogN)
function Func(n) {
for (let i = 0; i < n; i++) { //执行 n 次
for (let j = 0; j < n; j++) { // 执行 logn 次
j = j * 2;
}
}
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
自我介绍
上一篇
评论
