算法的时间复杂度

发布网友 发布时间：2022-03-23 17:09

我来回答

共1个回答

热心网友 时间：2022-03-23 18:39

当然应该是O(n^2)

----------------------------------------------------------

算法分析，就是复杂度的问题。

复杂度只算“最要命的”，比如，执行n^2的算法前来个快排根本不拖速度，n^2多的都豁出去了不在乎区区一个nlogn。

书里对复杂度进行了严格的定义，包括O()、o()、Θ()、Ω()四种符号。

简单地说，

O(n^2)就是顶破天了搞个n^2次；

o(n^2)就是天花板不到n^2，比n^2矮一点（比如希尔排序就是o(n^2)，因为它再倒霉也达不到n^2）；

Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2，比如所有基于比较的排序都是Ω(nlogn)；

Θ(n^2)就是说它即是O(n^2)又是Ω(n^2)，被天花板和水泥地夹在中间了，动不了了，就是它了。

参考资料：matrix67牛的博客