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

PHP中文网 • 2025年3月7日 12:23:33 • 编程技术 • 阅读 2

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  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 = 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 美分！！

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

发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2667813.html