| 常见排序算法的时间复杂度 | 您所在的位置：网站首页 › 数组排序的最好时间复杂度是 › 常见排序算法的时间复杂度 |
|
1、数组中插入元素的时间复杂度：
最好
最坏
平均
数组中插入元素
O(1)每次都在数组的末尾插入；
O(n)每次都在数组的头部插入；
2、常见排序算法的时间复杂度
假设数据量为n。 ~ 最好 最坏 平均 基本排序 冒泡（无标志位） O(n^2) O(n^2) O(n^2) 冒泡（有标志位） O(1)说明：已有序，只需1次； O(n^2)说明：逆序，标志位无效。同上 O(n^2)说明：以有序度作为测量。最好时，有序度为n，逆序度为n(n-1)/2；最差时相反；所以平均是n(n-1)/4； 插入 O(n)说明：已有序，只需比较n次，无需插入； O(n^2)说明：逆序，比较n次，插入n次，时间复杂度为O(n^2)；因为：数组插入的最坏时间复杂度为O(n)； O(n^2)说明：比较n次不可变，插入的平均时间复杂度：O(n)，所以总的平均时间复杂度为O(n^2)； 选择 O(n^2)说明：比较n次，查找最小元素n次，交换为常量 3； O(n^2)说明：同最好； O(n^2) 递归排序 归并 O(nlogn)说明：递归的时间复杂度推算公式见原文。merge的时间复杂度为O(n)（实际应该是2n）； O(nlogn)同左 O(nlogn)同左 快速 O(nlogn)说明：递归的时间复杂度推算公式见原文。获取分区点的时间复杂度为O(n)。遍历整个数组，然后交换元素。 O(n^2)特别极端的情况。 O(nlogn) 线性排序 桶 O(n) |
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 |