Big O Notation
n! >> 2^n >> n^2 >> nlogn >> n >> logn >> 1
排序算法
| 排序算法 | Best | Average | Worst | Space-Worst | Note |
|---|---|---|---|---|---|
| quicksort-快排 | O(nlogn) | O(nlogn) | O(n^2) | O(n) | space是递归调用的栈的空间 |
| mergesort-归并 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间，O(n+log) == O(n) |
| heapsort-堆排 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 因为堆排序是就地排序，空间复杂度为常数：O(1) |
| bubblesort-冒泡 | O(n^2) | O(n^2) | O(1) | 比较相邻的元素 | |
| insertionsort-插入 | O(n) | O(n^2) | O(n^2) | O(1) | 左边是排序好的，将新元素插入。 |
| selectionsort-选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 从剩下的里面选出最大/最小，放入尾部。 |
基础数据结构
堆
建堆(heapify) : O(n)
如何在数组上原地建立最大/小堆（heapify）
若有收获，就点个赞吧
0 人点赞
