冒泡法的算法最佳情况下的时间复杂度为什么是O(n)
我在许多书本上看到冒泡排序的最佳时间复杂度是O(n),即是在序列本来就是正序的情况下。
但我一直不明白这是怎么算出来的,因此通过阅读《算法导论-第2版》的2.2节,使用对插入排序最佳时间复杂度推算的方法,来计算冒泡排序的复杂度。
1. 《算法导论》2.2中对插入排序最佳时间复杂度的推算
在最好情况下,6和7总不被执行,5每次只被执行1次。因此,
时间复杂度为O(n)
2. 冒泡排序的时间复杂度
2.1 排序代码
public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j])
swap(arr, j, j + 1);
}
}
}
2.2 最佳情况
序列原本就是正序
2.3 最佳情况时间复杂度推算
语句 | cost | times |
i = 0, len = arr.length |
c1 | 1 |
i < len - 1 | c2 | n |
i++ | c3 | n - 1 |
j = 0 | c4 | n - 1 |
j < len - i - 1 | c5 | t(i=0) + t(i=1) + ... + t(i = n-2) |
j++ | c6 | t2(i=0) + t2(i=1) + ... + t2(i = n-2) |
arr[j + 1] < arr[j] | c7 | t3(i=0) + t3(i=1) + ... + t3(i = n-2) |
swap(arr, j, j + 1) | c8 | t4(i=0) + t4(i=1) + ... + t4(i = n-2) |
T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)] + c8[t4(i=0) + t4(i=1) + ... + t4(i = n-2)];
当序列原本就是正序时,8从不被执行。因此
T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)];
此时的时间复杂度应为O(n^2)。
可是网上和许多书上都写道是O(n),不知是否有人能帮我解答一下呢?
2.4 在Stackoverflow上问到答案了。
我原本的代码的时间复杂度确实应该是O(n^2),但算法可以改进,使最佳情况时为O(n)。改进后的代码为:
public void bubbleSort(int arr[]) {
boolean didSwap;
for(int i = 0, len = arr.length; i < len - 1; i++) {
didSwap = false;
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j]) {
swap(arr, j, j + 1);
didSwap = true;
}
}
if(didSwap == false)
return;
}
}
最新文章
- MVC Nhibernate 示例
- Dubbo_异常_Service启动时默认将方法注册到内网IP
- 基于Java的打包jar、war、ear包的作用与区别详解
- 代理延迟加载中proxy和弄no-proxy区别
- C++笔记----构造函数与析构函数(三)
- [转]LINQ之路系列博客导航
- 那些年不错的Android开源项目
- CCF真题之最大矩形
- 华东交通大学2016年ACM“双基”程序设计竞赛 1007
- spring-boot资料
- MapReduce中作业调度机制
- Front End中Javascript兼容问题收集(转)
- TCP/IP协议原理与应用笔记22:静态和动态路由选择
- 泰晓科技 +兰大开源社区 +程序动态分析---LINUX内核网站
- [Android]解决3gwap联网失败:联网请求在设置代理与直连两种方式的切换
- 程序员编程艺术:第三章续、Top K算法问题的实现
- oracle学习笔记(三) DCL 数据控制语言与 DDL 数据定义语言
- python作业练习
- metasploit生成payload的格式
- javascript数组的属性、方法和清空-最全!!!(必看)
热门文章
- 【bzoj2893】征服王
- Hdu2433 Travel
- SGU179 Brackets light
- Swagger2 添加HTTP head参数,解决用户是token信息保留
- Asp.Net Core 依赖注入默认DI,Autofac注入
- dp+分类讨论 Gym 101128E
- Qt undefined reference to ***
- 【bzoj】2326 [HNOI2011]数学作业
- 引用类型 ( 对象定义 )——Function 类型
- 127.0.0.1、localhost、0.0.0.0的区别