平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
N*LogN + K | N*N+K | N |
平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
N*K | N*k | N |
平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
N*logK | N*logK | k |
划分方法(主要区分轴的取法) | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
固定使用某一元素. 比如直接使用左边第一个元素 | N*logN | N*N | N(使用数组存储的话) |
三元取中法(或者说 中位数的中位数) | N | N | N |
五分化中项的中法 | N | N | N |
随机选取枢纽元法 | N | N | N |
n(数据集合大小) | 1000 | 10k | 10 000 k | 10 000 000 k(换算约10g) |
内存不受限 | 线性的快速划分 | 线性的快速划分 | 线性的快速划分 | 线性的快速划分 |
内存受限(2G) | 线性的快速划分 | 线性的快速划分 | 线性的快速划分 | 堆排序+归并排序 |
欢迎光临 Chinaunix (http://bbs.chinaunix.net/) | Powered by Discuz! X3.2 |