pascal 中 log(n)
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/07/08 16:28:13
pascal 中 log(n)
就是排序的平均时间(最快+最慢/2).
在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量.
稳定的
冒泡排序(bubble sort) — O(n2)
鸡尾酒排序 (Cocktail sort,双向的冒泡排序) — O(n2)
插入排序 (insertion sort)— O(n2)
桶排序 (bucket sort)— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 (merge sort)— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 (radix sort)— O(n•k); 需要 O(n) 额外记忆体
Gnome sort — O(n2) \x05
Library sort — O(n log n) with high probability,需要 (1+ε)n 额外记忆体
不稳定
选择排序 (selection sort)— O(n2)
希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 (heapsort)— O(n log n)
Smoothsort — O(n log n)
快速排序 (quicksort)— O(n log n) 期望时间,O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间,需要 额外的 O(n + k) 空间,也需要找到最长的递增子序列(longest increasing subsequence)
各算法的时间复杂度
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
其实当你知道某一个排序的算法是就可以用计算器的log算出来了
在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量.
稳定的
冒泡排序(bubble sort) — O(n2)
鸡尾酒排序 (Cocktail sort,双向的冒泡排序) — O(n2)
插入排序 (insertion sort)— O(n2)
桶排序 (bucket sort)— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 (merge sort)— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 (radix sort)— O(n•k); 需要 O(n) 额外记忆体
Gnome sort — O(n2) \x05
Library sort — O(n log n) with high probability,需要 (1+ε)n 额外记忆体
不稳定
选择排序 (selection sort)— O(n2)
希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 (heapsort)— O(n log n)
Smoothsort — O(n log n)
快速排序 (quicksort)— O(n log n) 期望时间,O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间,需要 额外的 O(n + k) 空间,也需要找到最长的递增子序列(longest increasing subsequence)
各算法的时间复杂度
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
其实当你知道某一个排序的算法是就可以用计算器的log算出来了