估计算法的运行时间（第 2 部分）

1.2 估计算法的运行时间

要估计算法的大o运行时间，这里有一些经验法则：

1. 恒定时间 – o(1):
   
   如果无论 ( n ) 有多大，算法都运行相同的时间，那么它是 o(1).

2. 线性时间 – o(n):
   
   运行 ( n ) 次的循环对 big o 运行时间贡献 ( n ) 倍。

3. 嵌套循环的乘法效应：
   
   如果循环是嵌套的，则乘以它们的运行时间。

4. 顺序循环的累加效应：
   
   如果一个循环跟随另一个循环，则添加它们的运行时间。

5. 对数时间 – 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 运行时间的规则摘要

1. 恒定时间 – o(1): 不依赖于 ( n ) 的操作。
2. 线性时间 – o(n): 迭代 ( n ) 次的单循环。
3. 对数时间 – o(log n): 每次迭代将循环变量除或乘以常数因子的循环。
4. 二次时间 – o(n²): 嵌套循环，每个循环运行 ( n ) 次。
5. 三次时间 – o(n³): 三个嵌套循环，每个循环运行 ( n ) 次。
6. 加法和乘法效应： 当循环是连续的时，它们的 big o 时间相加；嵌套时，它们会繁殖。

我相信应用这些经验法则并分析上面示例中所示的代码段，您可以有效地估计各种算法的 big o 运行时间。

如有任何问题，请随时发表评论。感谢您阅读我的 2 美分！！

以上就是估计算法的运行时间（第 2 部分）的详细内容，更多请关注php中文网其它相关文章！