回顾数据结构（Java版）——排序算法的分类以及时间复杂度

港控/mmm° 2023-06-08 03:13 31阅读 0赞

### 排序算法分类 ###

排序算法大致可以分为内部排序和外部排序。

1.  内部排序：在内存里进行的排序
    
     *  插入排序：直接插入排序和希尔排序
     *  选择排序：简单选择排序和堆排
     *  交换排序：冒泡排序和快速排序
     *  归并排序：采用分治法，将子序列排序并合并
     *  基数排序：属于分配排序法，和桶排序思路相同
2.  外部排序：内存结合外存进行的排序，一般在数据量很大的情况下，无法将数据全部加载在内存里

### 时间复杂度 ###

##### 时间频度 #####

一个算法中语句执行的次数就是语句频度或则是时间频度表示为T(n)，在大数据量面前可以忽略常数项，低次项和系数

##### 时间复杂度 #####

f(n)是一个假象出来的函数，如果T(n)/f(n)极限不为无穷，也就是一个常数时，那么O(f(n))就是算法的渐进时间复杂度，简称时间复杂度。

时间复杂度的计算方法  
例如：T（n）=2n^2+3n+9  
用1代替加法常数T（n）=2n2\+3n+1 ，去除低阶项 T（n）=2n2，去除高阶项的系数T（n）=n2，推出时间复杂度为O（n2）

##### 几种常见的时间复杂度及其比较 #####

1.  常数阶：无论代码执行多少行，没循环就是常数阶，不随着某个变量增长而增长。
2.  对数阶:比如下面这个例子，因为每次循环数字是按照3的倍数增长的，那执行次数就为log以3为底i的对数

while (i<n){
                i = i * 3;
            }

1.  线性阶：单层的for循环，执行次数为n+1
2.  线性对数阶：就是给对数阶外面套一个循环
3.  平方阶：双重循环
4.  立方阶：三重循环
5.  K次方阶：执行次数和n的K次方成正比
6.  指数阶：2n  
    ![在这里插入图片描述][20191015220043769.png]  
    关于平均时间复杂度，最坏时间复杂度，空间复杂度，平均时间复杂度比较难计算，并且最坏时间复杂度决定了算法的下线。  
    提升用户体验时间比较重要，因此可以适当通过空间换时间。

[20191015220043769.png]: /images/20230531/826fa78185ab4d009eddedea3c366525.png

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构---算法的时间复杂度和空间复杂度

看到这里就结束了，我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能一键三连支持一下博主，hhhh~我们下期见喽。

╰半橙微兮°/ 2024年04月24日 23:20/ 0 赞/ 112 阅读

相关【数据结构】算法的时间复杂度和空间复杂度

文章目录算法的时间复杂度和空间复杂度算法效率算法的复杂度时间复杂度

骑猪看日落/ 2024年04月01日 06:09/ 0 赞/ 96 阅读

相关排序算法分类排序算法时间复杂度、空间复杂度、稳定性

排序算法比较表格 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4u

你的名字/ 2024年02月19日 20:34/ 0 赞/ 83 阅读

相关 [时间复杂度]-排序算法的时间复杂度

我们经常可以看到这样的描述：软件=数据结构+算法，可见算法基础对于一个程序员的重要性。算法中，有两个基本概念：时间复杂度和空间复杂度。时间复杂度：描述算法执行消耗的时

今天药忘吃喽~/ 2023年09月24日 14:38/ 0 赞/ 107 阅读

相关数据结构--时间复杂度算法

数据结构–时间复杂度算法分别写出时间复杂度为o（1）、o（n）、o（n²）、o（log n）的算法： 1、O (1) include <io

青旅半醒/ 2023年07月03日 14:28/ 0 赞/ 33 阅读

相关回顾数据结构（Java版）——排序算法的分类以及时间复杂度

排序算法分类排序算法大致可以分为内部排序和外部排序。 1. 内部排序：在内存里进行的排序插入排序：直接插入排序和希尔排序选

港控/mmm°/ 2023年06月08日 03:13/ 0 赞/ 32 阅读

相关常见数据结构排序算法时间复杂度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NodWl4

客官°小女子只卖身不卖艺/ 2022年11月19日 09:54/ 0 赞/ 25 阅读

相关数据结构-算法-时间复杂度计算

算法的时间复杂度定义为：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法

快来打我*/ 2022年09月17日 07:28/ 0 赞/ 220 阅读

相关数据结构之算法时间复杂度

想要学会算法时间复杂度，那么就要先弄清楚几个概念。 1. 什么是算法时间复杂度？ 2. 它有什么用呢？ 3. 写法记作 T(n)=O(f(n)) T(n):语句

雨点打透心脏的1/2处/ 2022年05月25日 00:14/ 0 赞/ 262 阅读

相关数据结构和排序算法时间和空间复杂度

转自：[http://bigocheatsheet.com/][http_bigocheatsheet.com] ![43330618272_dbf88ff0bf_h.jpg

港控/mmm°/ 2022年05月20日 06:12/ 0 赞/ 127 阅读