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 部分）的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1491900.html
微信扫一扫 
支付宝扫一扫 
