CSP初赛知识

基础知识

计算机基础

位

$bit$（比特）即二进制位

字节

$1\ byte$ = $8\ bit$

字长

字长指的是 CPU 一次性能并行处理的二进制位数，$32$ 位的计算机最多可以处理 $32$ 位数据

前后缀表达式

举例：
中缀表达式：$1 + (2 + 3) × 4 - 5$
前缀表达式：$- +1 × + 2 3 4 5$
后缀表达式：$1 2 3 + 4 × + 5 -$

前缀符号前移，后缀符号后移

转换步骤：
1、按照运算符的优先级对所有的运算单位加括号
2、将运算符移动到对应括号的前面（前缀表达式）或后面（后缀表达式）
3、去掉括号，得到前缀或后缀表达式

时间复杂度

主定理

设一算法的时间复杂度表达式为 $T(n) = aT(\frac{n}{b})+f(n ^ d)$
可以使用主定理计算时间复杂度

$$T(n)= \begin{cases} O(n^d)\ \ \ \ \ \ \ \ \ \ \ \ \ \ d>log_ba\\ O(n^dlogn)\ \ \ \ \ \ d=log_ba\\ O(n^{log_ba})\ \ \ \ \ \ \ \ \ d<log_ba\\ \end{cases}$$

技巧&细节

1、运行错误 $\neq$ 结果错误，前者只要程序可以运行即可
2、压缩率指的是压缩为原本的百分比，而不是压缩了多少