Prologue
这本来是洛谷网校前两课中两节的内容，我觉得很有意思，于是就拎出来单独发了。
其实主定理是第二课分治的时候讲的，但是很有趣，和时间复杂度也有关系，就归到第一节里面了。
但是主定理我无法完全理解，我只把我理解了的放了上去 awa
这里多行 $\LaTeX$ 环境真的用不了，会被强制合并成一行。
本文同步发表在 洛谷专栏。
时间复杂度
大 O（Big-Oh）表示法
表示为 $O(f(n))$（渐进时间复杂度），其中 $f(n)$ 是一个函数，$f(n) = n\mathrel{/}n^2\mathrel{/}n^3\mathrel{/}n \log n\mathrel{/}\cdots$。
表现的是一个趋势，而非具体运行次数。
$O(n)$ 表示存在一个整数 $c$，实际运行次数 $T(n) \le cn$。
对数
定义为 $$ \boxed{x = \log_a b, a^x = b}\tag{1} $$ 换底公式： $$ \boxed{x = \log_a b = \dfrac{\log_c b}{\log_c a}}\tag{2} $$ 其中 $c$ 为任意数。
对于一个复杂度 $O(\log_a b)$，底数 $a$ 可以省略。将其代入 $(2)$，$\log_c a$ 为定值，因此可以省略。
证明如下：
设 $x = \dfrac{\log_c b}{\log_c a}$，则 $$ c^x = c^\frac{\log_c b}{\log_c a} = (c^{\log_c b})^\frac{1}{\log_c a} = b^\frac{1}{\log_c a}\tag{3} $$ 因 $\dfrac{1}{\log_a c} = \log_c a$，所以代入 $(3)$ 得 $$ \boxed{c^x = b^{\log_a c}\tag{4}} $$ 将 $(1)$ 代入 $a^x$ 得 $$ a^x = (c^{\log_c a})^x = (c^x)^{\log_c a} = c^{x \cdot \log_c a} = c^{\frac{\log_c b}{\log_c a} \cdot log_c a} = c^{log_c b} = b $$ 所以得 $$ \boxed{a^x = b} $$ 即 $(2)$。证毕。
渐进时间复杂度的几种表示
渐进复杂度的几种表示：$O(f(n))$、$\Theta(f(n))$、$\Omega(f(n))$。
- $O(f(n))$：算法处理规模为 $n$ 的数据时，运算次数 $T(n)$，$\forall n$，$\exists c>0$ 使得 $T(n) \le c\cdot f(n)$，此时我们称算法时间复杂度为 $O(f(n))$ 的。
- $\Omega(f(n))$：算法处理规模为 $n$ 的数据时，运算次数 $T(n)$，$\forall n$，$\exists c>0$ 使得 $T(n) \ge c\cdot f(n)$，此时我们称算法时间复杂度为 $\Omega(f(n))$ 的。
- $\Theta(f(n))$：算法既满足 $O(f(n))$，也满足 $\Omega(f(n))$。$c$ 可以不相等。
主定理（Master Theorem）
前置知识：三种渐进时间复杂度。
简单理解：一个处理规模为 $n$ 的算法，分成 $b$ 个子问题求解，求解这些子问题总用时为 $aT\left(\dfrac{n}{b}\right)$，合并子问题时的用时为 $f(n)$，求这时的复杂度。通过两者的大小关系来求解最终的复杂度。
杂项
- 调和级数：$1 + \frac12 + \frac13 + \dotsb + \frac1n = O(\log n)$。
- 多项式级算法：$O(n^a\log^b n)$。
位运算
制约
- 定义最右边一位为最低位，称作第 $0$ 位。
- 定义最左边一位为最高位，称作第 $n - 1$ 位。
- 两操作数位数相同，若不相同在左边补零。规定 $x_i$ 表示 $x$ 的第 $i$ 位。
- 不讨论负数的位运算。
逻辑运算
- 与：$x \land y = \begin{cases}1&x, y = 1\newline 0&\text{otherwise.}\end{cases}$
- 或：$x \lor y = \begin{cases}0&x, y = 0\newline 1&\text{otherwise.}\end{cases}$
换言之，$x, y$ 中有一个是 $1$ 就为 $1$。 - 异或：$x \oplus y = \begin{cases}1&x \ne y \newline 0&x=y.\end{cases}$
- 非：$\neg x = \begin{cases}1&x = 0 \newline 0&x = 1.\end{cases}$
位运算
- 按位与
x & y：按位做逻辑与。 - 按位或
x | y：按位做逻辑或。 - 按位异或
x ^ y：按位做逻辑异或。 - 取反
~x：按位做逻辑非。 - 左移
x << y：$x$ 向左移 $y$ 位，高位抹去，低位补零。 - 右移
x >> y：$x$ 向右移 $y$ 位，低位抹去，高位补零。
对于左移右移，$\verb|x « y| = x \cdot 2^y$，$\verb|x » y| = \left\lfloor\dfrac{x}{2^y}\right\rfloor$。
并且，$\verb|1 « i| = 2^i$。但是，当 $i > 30$ 时，要开 long long 或 unsigned long long。可以用 1ll、1llu 代表 (long long)1、(unsigned long long)1。
单点修改
- $x_i$ 改为 $1$：
x |= 1 << i。 - $x_i$ 改为 $0$，保证 $x_i = 1$：
x ^= 1 << i。 - $x_i$ 改为 $0$，不保证 $x_i = 1$：
x &= (~(i << 1))。
位运算与集合
- 交集：$A \cap B = \verb|A & B|$。
- 并集：$A \cup B = \verb!A | B!$。
- 补集：$\bar A = \complement_U A = \verb|~A|$。
- 对称差（只在两者之一出现的元素）：$A \mathbin{\Delta} B = \verb|A ^ B|$。
集合可以理解为一个二进制串。
bitset
一个二进制串数组，每个元素是一个二进制位，支持除了 ~ 以外的位运算。
std::bitset<N> s：创建长度为 $N$（常量）的bitset。s.set(i, 0/1)：第 $i$ 位设为 $0\mathrel{/} 1$，不写设 $1$。可以判断是否越界，越界 RE。s.test(i)：返回 $s_i$。可以判断是否越界，越界 RE。s.count()：数里面有多少个 $1$。s.reset()：清空，设为全 $0$。s.flip()：取反运算。
先 s.reset() 再 s.flip() 可以得到全 $1$。
原理是 $\dfrac{n}{64}$ 个 unsigned long long。
一次位运算 $O(n)$，常数 $\dfrac{1}{64}$。时间复杂度 $O\left(\dfrac{n}{w}\right)$，一般 $w = 64$。空间复杂度 $O\left(\dfrac{n}{w}\right)$。
B3695 集合运算 3
经过读题，发现操作可以被分成两大类。
- 每个元素都加上 / 减去某一个数。
- 求交集 / 并集 / 对称差。
我们把有 $x$ 这个元素表示为第 $x$ 位是 $1$。
那么操作 1 可以被理解为左移、右移，而操作 2 可以被理解为与、或、异或。
可以使用 bitset 维护，但是 bitset 的长度只能是一个定值，位移的时候无法保证元素被正确地抹去。所以可以再开一个 bitset，长度相同，$0 \dots m - 1$ 为 $1$，其余为 $0$。每做位移后，将其与原 bitset 做与运算。
Last modified on 2024-07-17