初赛笔记1
1.Linux 命令
ls : 列出目录下文件夹
cd：切换目录
mkdir：新建目录
rm：删除
cp：复制
mv：移动
rmdir：删除目录
2.排序方法
| 名称 | 最好复杂度 | 最坏复杂度 | 平均复杂度 | 是否稳定 |
|---|---|---|---|---|
| 插入排序 | O ( n ) O(n) O(n) | O ( n 2 ) O(n ^ 2) O(n2) | O ( n 2 ) O(n ^2) O(n2) | 稳定 |
| 冒泡排序 | O ( n ) O(n) O(n) | O ( n 2 ) O(n ^ 2) O(n2) | $ O(n^2)$ | 稳定 |
| 选择排序 | O ( n ) O(n) O(n) | O ( n 2 ) O(n ^ 2) O(n2) | $ O(n^2)$ | 不稳定 |
| 归并排序 | O ( n ) O(n) O(n) | O ( n log ( n ) ) O(n \log(n)) O(nlog(n)) | O ( n log ( n ) ) O(n \log(n)) O(nlog(n)) | 稳定 |
| 快速排序 | O ( n ) O(n) O(n) | O ( n 2 ) O(n ^ 2) O(n2) | O ( n log ( n ) ) O(n \log(n)) O(nlog(n)) | 不稳定 |
| 桶排 | / | O ( n 2 ) O(n^2) O(n2) | O ( n + n 2 k + k ) O(n + \frac{n^2}{k} + k) O(n+kn2+k)， k k k为分块数量 | 稳定 |
| 计数排序 | / | O ( n + w ) O(n + w) O(n+w) | O ( n + w ) O(n + w) O(n+w) ， w w w为值域 | 稳定 |
| 基数排序 | / | O ( n k ) O(nk) O(nk) | O ( n k ) O(nk) O(nk), k k k是位数 | 稳定 |
| 希尔排序 | / | O ( n 2 ) O(n^2) O(n2) | O ( n log 2 ( n ) ) O(n \log^2(n)) O(nlog2(n)) | 不稳定 |
| 堆排 | / | O ( n log ( n ) ) O(n \log(n)) O(nlog(n)) | O ( n log ( n ) ) O(n \log(n)) O(nlog(n)) | 不稳定 |
3.有关树
完全 n n n 叉树：除了最后一层之外其他都是满的
满 n n n 叉树：包括最后一层都是满的
前序遍历：根，左儿子，右儿子
后序遍历：左儿子，右儿子，根
中序遍历：左儿子，根，右儿子