当前位置: 首页> 游戏> 网游 > JS【详解】时间复杂度

JS【详解】时间复杂度

时间:2025/7/11 8:50:45来源:https://blog.csdn.net/weixin_41192489/article/details/139355251 浏览次数:0次

时间复杂度是从时间维度描述一段代码的复杂程度,由一段代码中执行频次最高的语句决定,用大O符号表述。

时间复杂度的分类

从低到高依次是:

  • 常数时间复杂度 O(1):无论问题规模如何变化,算法的运行时间都保持不变。

  • 线性时间复杂度 O(n):当输入规模n线性增加时,算法的运行时间呈现出线性增长趋势。

  • 对数时间复杂度 O(log n):当输入规模n呈指数增长时,算法的运行时间呈对数增长趋势。

  • 平方时间复杂度 O(n^2):当输入规模n线性增加时,算法的运行时间呈现出平方增长趋势。

  • 立方时间复杂度O(n^3):当输入规模n线性增加时,算法的运行时间呈现出立方增长趋势。

  • 指数时间复杂度 O(2^n):当问题规模成指数增长时,算法的运行时间将会急剧增加

O(1)

O(1) 不是说只执行1次,而是对常量级时间复杂度的一种表示法。一般情况下,只要算法里没有循环和递归,就算有上万行代码,时间复杂度也是O(1)

(function () {console.log("你好");
})();
// 时间复杂度还是 O(1)
(function () {console.log("你好");console.log("你好");
})();

O(n)

只有一层循环或者递归等,时间复杂度就是 O(n)

function test(n) {for (let i = 0; i < n; i++) {console.log(i);}
}

O(n^2)

嵌套循环的时间复杂度就是 O(n^2)

function test(n) {for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {console.log(i, j);}}
}

多种复杂度并列在一起时,只取执行次数最高的语句,即取最高项

// 最终的时间复杂度以高的为准,是 O(n^2)
function test(n) {//   单循环的时间复杂度是 O(n)for (let i = 0; i < n; i++) {console.log(i);}//   嵌套循环的时间复杂度是 O(n^2)for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {console.log(i, j);}}
}

O(logn)

二分法的时间复杂度是 O(logn),以下两种情况都是。

function test(n) {while (n > 1) {n = n / 2;console.log(n);}
}
function test(n) {for (let i = 1; i < n; i = i * 2) {console.log(i);}
}

O(nlogn)

二分嵌套一个单循环,即时间复杂度O(nlogn)

function test(n) {for (let i = 1; i < n; i = i * 2) {for (let j = 0; j < n; j++) {console.log(i, j);}}
}
关键字:JS【详解】时间复杂度

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: