专栏文章

csp初赛复习记录

2025/09/13 16:31个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @minx1940
此快照首次捕获于: 2025/12/02 09:45
此快照最后确认于: 2025/12/02 09:45

Linnux

切换目录命令cd
cd(change directory)
列出文件列表的命令 ls
ls(list)是一个非常常用的命令,用来显示当前目录下的内容.
创建目录和移除目录mkdir rmdir
mkdir(make directory)创建目录
rmdir(remove directory)移除目录
打印当前工作的目录pwd
pwd(prinlt work directory)
tail显示文件后几行的内容。
touch创建一个空文件
mv(move) 移动文件
cp(copy) 拷贝文件
rm删除文件
tar将用户所指定的文件或目录打包成一个文件

欧拉回路：通过图的每一条边，最终回到起点的路径。

欧拉通路：可以不回到起点
一个自然数 n ，计算 n 的逆元用扩展欧几里得算法
有 n 个键值的哈希表查找一个元素的时间复杂 $O(n)$
一棵 ℎ 层的完全二叉树，该树最多包含 $2^h−1$ 个结点
队列是一种先进先出（FIFO）的线性结构
哈夫曼树的构造过程主要是为了实现图的广度优先搜索
散列表是一种通过散列函数将关键字映射到存储位置的数据结构
二叉树是一种每个结点最多有两个子结点的树结构
连通无向图中，完全三叉树一定可以用不超过两种颜色进行染色

10.对比常见排序算法性能

排序算法	最优时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
快速排序	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	❌ 否
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	✅ 是
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	❌ 是
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 否
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 否
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	❌ 是
希尔排序	$O(n \log n)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	❌ 否
计数排序	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(k)$	✅ 是
桶排序	$O(n + k)$	$O(n + k)$	$O(n^2)$	$O(n + k)$	✅ 是
基数排序	$O(d(n + k))$	$O(d(n + k))$	$O(d(n + k))$	$O(n + k)$	✅ 是

g++ -o main main.cpp ,能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件
奇数个结点的树一定只有一个重心
存在环的图无法拓扑排序

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...