这篇文章是对上周发的 11大排序 这个视频中提到的 时间复杂度 和 空间复杂度 进行一个解析，有问题可以在评论区提，觉得我说得不对也可以在评论区指出哈。
当 i = 0 的时候，j 从 1 到 n-1，内层循环执行次数为 n-1 次；
当 i = 1 的时候，j 从 2 到 n-1，内层循环执行次数为 n-2 次；
... （根据数学归纳法）
当 i = n-2 的时候，j 从 n-1 到 n-1，内层循环执行次数为 1 次；
所以总的执行次数就是 (1 + (n-1)) * (n-1) / 2 = n * (n - 1) / 2；
所以时间复杂度就是 O(n^2)
由于在进行循环计算的时候
只用到了一个 min 作为额外变量
所以空间复杂度就是 O(1)
内层循环做的事情
是在一个区间内寻找一个最小值
然后把最小值更新为另一个值
这样的操作
可以用线段树来进行优化
使得查找最小值和更新区间值的操作
内层循环的时间复杂度降为 O(logn)
所以总的时间复杂度就是 O(nlogn)
当 i = n-1 时，j 从 0 到 n-2，内层循环数是 n-1
当 i = n-2 时， j 从 0 到 n-3，内层循环数是 n - 2
...（根据数学归纳法）
当 i = 1 时， j 从 0 到 0，内层循环数是 1
所以总的执行次数就是 (1 + (n-1)) * (n-1) / 2 = n * (n - 1) / 2；
所以时间复杂度就是 O(n^2)
由于在进行循环计算的时候
没有用到额外变量
所以空间复杂度就是 O(1)
内层循环中
如果发现已经完全有序了
则置一个标志位
并且无须继续排序
这就是优化
当原本就是一个升序序列时
内层循环每次只需要执行一次
总共执行 n 次
所以时间复杂度为 O(n)
当原本是一个降序序列时
内层循环每次需要执行 i 次
总共需要执行 (1 + n) * n / 2
所以时间复杂度为 O(n^2)
然而我们在说时间复杂度的时候
往往说的是最坏时间复杂度
所以这个算法的时间复杂度
就是 O(n^2)
由于没有用到任何的额外变量
所以空间复杂度是 O(1)
插入排序可以利用希尔排序进行优化
下文就会讲到了
假设比较和赋值的时间复杂度为O(1)
首先讨论归并排序最重要的子程序
是一个 O(n) 的归并
给定两个大小为 n1 和 n2 的排序树组 A 和 B
我们可以在 O(n) 时间内
将它们有效地归并成一个大小为 n = n1 + n2 的排序数组
那么请问这个归并过程
被调用了多少次？
由于每次都是对半切
所以整个归并过程类似于一棵二叉树的构建过程
次数就是二叉树的高度即 log n
所以归并排序的时间复杂度为 O(nlogn)
由于归并排序在归并过程中
需要额外的一个辅助数组
且最大长度为序列长度
所以归并排序的空间复杂度为 O(n)
时间复杂度
已经是比较排序中最优的了
无须继续优化
但是空间复杂度是可以优化的
由于在排序的过程中
需要额外的一个辅助数组
所以申请辅助数组内存空间
带来的空间消耗会比较大
所有辅助数组干的事情
都可以在传参进去的数组上进行
这样就省去了内存的频繁申请和释放
上面说了
时间复杂度一定要看最坏情况
所以如果数据导致
分成 x 个桶
但是只有第一个桶有元素
其他桶都没有元素
这时候就会退化成 O(n^2) 的选择排序
所以每个桶中的排序
我们可以采用归并排序
这样一来
最坏情况下
时间复杂度也只是 O(nlogn)
由于要把所有元素
放到桶中
所以总共需要放置的空间为 O(n)
于是空间复杂度就是 O(n)
桶排序对数据要求比较高
并不是适用所有数据类型的排序
所以局限性也比较大
一般不会直接用
除非数据分布比较特殊
一般用到的是 计数排序 和 基数排序
由于计数排序
将所有数字哈希到了哈希表中
所以插入和查找的时间复杂度为O(1)
每个数字插入一次取出一次
总的时间复杂度为 O(n)
假设序列中的元素
都是整数并且返回为 [a, b]
那么令 m = b - a + 1
空间复杂度就是 O(m)
由于计数排序对数据范围是有要求的
如果是非整数
则排序过程需要乘上对应的精度
如果数值太大
则无法完成我们的预期
如果出现了负数
需要加上偏移
总的来说
虽然时间复杂度非常优秀
但是对数据本身的要求会很高
和数字的数据范围有关
假设一个数字最高位为 m 位数
那么 while 循环 m 次
每次内部执行 n 次
总的时间复杂度为 O(mn)
需要建立10个桶
每个桶的元素加起来
总的大小为 n
所以空间复杂度为 O(n)
基数排序是对计数排序的优化
计算数字再大
也可以映射到桶中
容错性会更好
如果本身就是升序的序列
那么快速排序的时间复杂度是 O(n^2)
也就是最坏时间复杂度
类似冒泡排序
使用交换的方式进行排序
如果不算堆栈的消耗
空间复杂度为 O(1)
由于基准点采用了随机
所以基本不可能次次都是最坏情况
平均时间复杂度降为 O(nlogn)
非常优秀的算法
唯一的缺点就是
它是不稳定的
时间复杂度分析
网上说是 O(n^(2/3))
具体怎么证明（先留个坑，今天太困了，留给评论区）
希尔排序是原地排序
所以空间复杂度为 O(1)
时间复杂度分析
由于堆是一棵完全二叉树
所以树的高度为 logn
所以每一次操作最多执行 logn次
所以时间复杂度为 O(nlogn)
由于没有采用任何的空间
所以空间复杂度为 O(1)
到此这篇莫队算法复杂度（莫队时间复杂度）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/jszy-gxgz/61751.html