1.2 估计算法的运行时间
要估计算法的大o运行时间，这里有一些经验法则：
恒定时间 – o(1):
如果无论 ( n ) 有多大，算法都运行相同的时间，那么它是 o(1).线性时间 – o(n):
运行 ( n ) 次的循环对 big o 运行时间贡献 ( n ) 倍。嵌套循环的乘法效应：
如果循环是嵌套的，则乘以它们的运行时间。顺序循环的累加效应：
如果一个循环跟随另一个循环，则添加它们的运行时间。对数时间 – o(log n):
如果循环变量以 ( i = i times 2 ) 或 ( i = i / 3 ) 等方式增加，而不是按恒定量变化（如 ( i++ ) 或 ( i -= 2 ) ），则为 big o 运行时间贡献 log ( n ) 因子。
计算 big o 运行时间的示例
下面是几个示例，演示了如何计算不同代码段的 big o 运行时间。所有示例都涉及数组，我们假设 ( n ) 是数组的长度。
1.对数组中的条目求和
let total = 0;
for (let i = 0; i < a.length; i++) {
total += a[i];
}
运行时间：
此代码运行时间为o(n)。这是一个简单的循环，遍历数组的每个元素一次。
2.嵌套 for 循环
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length; j++) {
console.log(a[i] + a[j]);
}
}
运行时间：
这是两个普通循环，每个循环运行 ( n = a.length ) 步骤。由于它们是嵌套的，因此它们的运行时间成倍增加，导致总体运行时间为 o(n²)。对于外循环的每次 ( n ) 次迭代，内循环都会运行 ( n ) 次。
3.三个嵌套循环
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length - 1; j++) {
for (let k = 0; k < a.length - 2; k++) {
console.log(a[i] + a[j] * a[k]);
}
}
}
运行时间：
此代码运行时间为o(n³)。从技术上讲，由于第二个和第三个循环没有运行数组的完整长度，因此我们可以将其写为 o(n(n - 1)(n - 2))。然而，我们关注最重要的项，即 o(n³)，因为随着 ( n ) 的增长，低阶项变得微不足道。
4.顺序循环
let count = 0, count2 = 0;
for (let i = 0; i < a.length; i++) {
count++;
}
for (let i = 0; i < a.length; i++) {
count2 += 2;
}
运行时间：
这里的运行时间是 o(n + n) = o(2n)，它简化为 o(n) 因为我们忽略了 big o 表示法中的常量。
5.恒定时间操作
let w = a[0]; let z = a[a.length - 1]; console.log(w + z);
运行时间：
这里的运行时间是o(1)。关键思想是运行时间不依赖于 ( n )。无论数组有多大，此代码的运行时间始终相同。
6.不断迭代的循环
let c = 0;
let stop = 100;
for (let i = 0; i < stop; i++) {
c += a[i];
}
运行时间：
尽管存在循环，此代码仍会在 o(1) 时间内运行。无论数组有多大，循环始终运行 100 次。请注意，a.length 从未出现在代码中，使得运行时间恒定。
7.对数循环
let sum = 0;
for (let i = 1; i < a.length; i *= 2) {
sum += a[i];
}
运行时间：
此代码运行时间为o(log n)。循环变量呈指数增长：1, 2, 4, 8, 16, 32, 64, 128, ...只需10步即可达到1000，20步即可达到100万，30步即可达到10亿。
到达 ( n ) 的步数由求解 ( 2^x = n ) 决定，其解为 log2(n) （通常写为 log(n)).
8.具有对数内循环的嵌套循环
let n = a.length;
for (let i = 0; i < n; i++) {
let sum = 0;
let m = n;
while (m > 1) {
sum += m;
m /= 2;
}
}
运行时间：
该代码的运行时间为 o(n log n)。外部循环是一个标准循环，贡献一个因子 ( n )，而内部 while 循环是对数循环，因为循环变量每次减半。将这些因素相乘得到 o(n log n).
9.循环组合
let total = 0;
let i = 0;
while (i < a.length) {
i++;
total += a[i];
}
for (let i = 0; i < a.length / 2; i++) {
for (let j = a.length - 1; j >= 0; j--) {
total += a[i] * a[j];
}
}
运行时间：
运行时间为o(n²)。计算方法如下：
- while 循环在 o(n) 时间内运行。
- 嵌套的 for 循环运行时间为 o(n * (n/2)) = o(n²) 时间。
- 将它们加在一起得到o(n + n²)。然而，我们专注于主导项并放弃常数，从而得到 o(n²).
估算 big o 运行时间的规则摘要
- 恒定时间 – o(1): 不依赖于 ( n ) 的操作。
- 线性时间 – o(n): 迭代 ( n ) 次的单循环。
- 对数时间 – o(log n): 每次迭代将循环变量除或乘以常数因子的循环。
- 二次时间 – o(n²): 嵌套循环，每个循环运行 ( n ) 次。
- 三次时间 – o(n³): 三个嵌套循环，每个循环运行 ( n ) 次。
- 加法和乘法效应： 当循环是连续的时，它们的 big o 时间相加；嵌套时，它们会繁殖。
我相信应用这些经验法则并分析上面示例中所示的代码段，您可以有效地估计各种算法的 big o 运行时间。
如有任何问题，请随时发表评论。感谢您阅读我的 2 美分！！
