排序算法
# 排序算法
# 排序算法的介绍
排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程。
# 排序的分类
- 内部排序 指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。
- 外部排序法 数据量过大,无法全部加载到内存中,需要借助**外部存储(文件等)**进行排序。
- 常见的排序算法分类
# 算法的时间复杂度
# 度量一个程序(算法)执行时间的两种方法
- 事后统计的方法 这种方法可行,但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较那个算法速度更快。
- 事前估算的方法 通过分析某个算法的时间复杂度来判断哪个算法更优.
# 时间频度
- 基本介绍 时间频度:一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
- 举例说明-基本案例 比如计算.1-100所有数字之和,我们设计两种算法:
- 举例说明-忽略常数项
结论:
- 2n+20 和 2n 随着 n 变大,执行曲线无限接近, 20 可以忽略
- 3n+10 和 3n 随着 n 变大,执行曲线无限接近, 10 可以忽略
- 举例说明-忽略低次项
结论:
- 2n2+3n+10 和 2n2 随着 n 变大,执行曲线无限接近,可以忽略 3n+10
- n2+5n+20 和 n2 随着 n 变大,执行曲线无限接近,可以忽略 5n+20
- 举例说明-忽略系数
结论:
- 随着 n 值变大,5n2+7n 和 3n2+2n,执行曲线重合,说明这种情况下,5 和 3 可以省略。
- 而 n3+5n 和 6n3+4n,执行曲线分离,说明多少次方式关键。
# 时间复杂度
- 一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用 T(n) 表示,若有某个辅助函数
f(n)
,使得当n
趋近于无穷大时,T(n)/ f(n)
的极限值为不等于零的常数,则称f(n)
是T(n)
的同数量级函数。记作 T(n)=O( f(n)) ,称o( f((n))
为算法的渐进时间复杂度,简称时间复杂度。 T(n)
不同,但时间复杂度可能相同。如: T(n)=n2+7n+6 与 T(n)=3n2+2n+2 它们的T(n)不同,但时间复杂度相同,都为O(n2)。- 计算时间复杂度的方法:
- 用常数Ⅰ代替运行时间中的所有加法常数‘T(n)=n2+7n+6 => T(n)=n2+7n+1
- 修改后的运行次数函数中,只保留最高阶项T(n)=n2+7n+1 => T(n)= n2
- 去除最高阶项的系数‘T(n)= n2 => T(n)= n2 => O(n2)
# 常见的时间复杂度
- 常数阶 O(1)
- 对数阶 O(log2n)
- 线性阶 O(n)
- 线性对数阶 O(nlog2n)
- 平方阶 O(n2)
- 立方阶 O(n3)
- k 次方阶 O(nk)
- 指数阶 O(22)
常见的时间复杂度对应的图:
说明:
- 常见的算法时间复杂度由小到大依次为:O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(nk)<O(2n),随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低
- 从图中可见,我们应该尽可能避免使用指数阶的算法
常数阶 O(1)
无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1)
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示它的时间复杂度。
对数阶 O(log2n)
int i = 1;
while(i < n){
i = i * 2;
}
说明:在while循环里面,每次都将 i 乘以 2 ,乘完之后,i 距离 n 就越来越近了。假设循环 x 次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n ,那么x=logzn也就是说当循环 log2n 次以后,这个代码就结束了。因此这个代码的时间复杂度为: O(log2n)。O(log2n) 的这个2时间上是根据代码变化的,i=i*3,则是O(log3n).
线性阶 O(n)
for(i = 1;i <= n; ++i) {
j = 1;
j++;
}
说明:这段代码,for 循环里面的代码会执行 n 遍,因此它消耗的时间是随着 n 的变化而变化的,因此这类代码都可以用 O(n) 来表示它的时间复杂度
线性对数阶 O(nlogN)
for(m = 1;m < n;m++) {
i = 1;
while(i < n) {
i = i * 2;
}
}
说明:线性对数阶 O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了o(nlogN)
平方阶 O(n2)
for(x = 1;i <= n;x++) {
for(i = 1;i <= n;i++) {
j = 1;
j++;
}
}
说明:平方阶 O(n2) 就更容易理解了,如果把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n2),这段代码其实就是嵌套了2层 n 循环,它的时间复杂度就是 O(n*n), 即**O(n2)**如果将其中一层循环的 n 改成 m ,那它的时间复杂度就变成了 O(m*n)
立方阶O(n³)、K次方阶O(nk)
# 平均时间复杂度和最坏时间复杂度
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致,和算法有关(如图:)。
# 算法的空间复杂度简介
# 基本介绍
- 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模n的函数。
- 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法,基数排序就属于这种情况
- 在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(
redis
,memcache
)和算法(基数排序)本质就是用空间换时间.
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023