算法的时间复杂度冒泡排序法最坏要比较0.5n(n+1)次，答案说时间复杂度为O（0.5n(n+1))但书上讲时间复杂度时说取得是最高次相，这样子说的话答案就应该是O(n平方）到底哪个对啊？

Question

算法的时间复杂度
冒泡排序法最坏要比较0.5n(n+1)次，
答案说时间复杂度为O（0.5n(n+1))
但书上讲时间复杂度时说取得是最高次相，这样子说的话答案就应该是
O(n平方）
到底哪个对啊？

Answer 1

当然应该是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)，被天花板和水泥地夹在中间了，动不了了，就是它了。