冒泡排序法的时间复杂度怎么算? f(n)为什么等于n+4*n^2⼀2?

冒泡排序法的时间复杂度怎么算?f(n)为什么等于n+4*n^2/2?
2025-01-08 12:40:44
推荐回答(1个)
回答1:

外层循环n-1次,有1句赋值,内层循环n-i次,有4句赋值。
内层循环总的次数用等差数列求和公式算一下就是(1+(n-1))*(n-1)/2=n*(n-1)/2≈n^2/2
所以f(n)≈1 * n + 4 * n^2/2
存在常数c使得当n很大时,f(n)<=c*n^2,所以时间复杂度是O(n^2)