冒泡排序法的时间复杂度怎么算？ f(n)为什么等于n+4*n^2/2?
答案:1 悬赏:60 手机版
解决时间 2021-04-26 12:48
- 提问者网友：留有余香
- 2021-04-26 08:53
冒泡排序法的时间复杂度怎么算？ f(n)为什么等于n+4*n^2/2?
最佳答案
- 五星知识达人网友：笑迎怀羞
- 2021-04-26 10:08
外层循环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)
内层循环总的次数用等差数列求和公式算一下就是(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)
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯