技术杂记 腾讯云+Nginx+Typecho搭建个人主页 2021-12-10 浏览量 1241 评论数 1 主要是注意版本问题，上typecho的时候注意php的版本，别8.0以上就行（也许分析分析改一改也行，但我不会，换个版本这种简单的操作更适合我，省略好多泪）。 - 阅读全文 -
数据结构与算法 12. 排序 2021-07-29 浏览量 601 暂无评论 [TOC] ## 12.1 快速排序：算法A 分而治之 将序列分为两个子序列：$S = S_L + S_R，max(S_L) \le min(S_R)$ 在子序列递归地排序之后，原序列自然有序：$sorted(S) = sorted(S_L) + sorted(S_R)$ 与归并的区别在于： - 归并的计算量和难点在于**合** - 快排在于**分** ### 轴点 在序列中的特殊元素：左/右侧元素，均不比它大/小 若能知道轴点，则 ```cpp template <typename T> void Vector<T>::quickSort(Rank lo, Rank hi) { if (hi - lo < 2) return; Rank mi = partition(lo, hi - 1); quickSort(lo, mi); quickSort(mi + 1, hi); } ``` 然而轴点未必存在 快排就是将所有元素逐个转换为轴点的过程 ### 构造轴点 ```cpp template <typename T> Rank Vector<T>::partition(Rank lo, Rank hi) { // 随机选取候选轴点 swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]); pro = _elem[lo]; while (lo < hi) { // 仍要加上lo < hi，避免空闲位置产生影响，比如4[4]9，此时4<=5，lo仍会加1，指向9 // 但是可以把 <= 改为<吧，不行，这不是等不等于的事 // 更一般地讲，如果最后lo=hi指向的元素仍小于pro，则lo会再加1 while (lo < hi && pro <= _elem[hi]) hi--; _elem[lo] = _elem[hi]; while (lo < hi && elem[lo] <= pro) lo++; _elem[hi] = _elem[lo]; } // 这一步之前，lo=hi的位置元素是小于等于pro的，那就和pro交换 _elem[hi] = pro; return hi; ｝ ``` **缺点**： - 不稳定 - 划分不均衡 划分均衡的情况下，接近归并排序，$O(nlogn)$ 划分极不均衡的情况下，与冒泡相当，$O(n^2)$ 平均性能：$O(nlogn)$ 就算使用随机选取的方法，也只是降低最坏情况的概率，不能杜绝 ### 变种 #### 不变性 $$ S = [lo] + L(lo, mi] + G(mi, k) + U[k, hi] \\ L \lt pivot \leq G $$ #### 单调性  #### 实现 ```cpp template <typename T> Rank Vector<T>::partition(lo, hi) { swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]; pivot = _elem[lo]; Rank mi = lo; for (Rank k = lo + 1; k <= hi; k++) if (_elem[k] < pivot) swap(_elem[++m], _elem[k]); swap(_elem[lo], _elem[mi]); return mi; } ``` #### 实例  #### 综合评价 - 就地算法 - 线性复杂度 - 稳定性不能保证 ## 12.2 选取：众数 - 第k个大的元素 - 中位数 - 众数 如何绕开排序，直接选取？ **众数**：无序向量中，若有**一半以上**元素为m，则称之为众数。 **必要性**：众数若存在，则亦必为中位数。 **减而治之：** 每次迭代移出某元素占一半的前缀P，则若众数存在，必在剩下的向量中 ```cpp template <typename T> T majEleCandidate(Vector<T> A) { T maj; // c为前缀中首元素数量与其他元素数量的差值，差值为0表明可以剪去 for (int c = 0, i = 0; i < A.size(); i++) if (c == 0) { maj = A[i]; c = 1; } else maj == A[i] ? c++ : c--; return maj; // } ``` ### 通用算法 #### 堆A 建堆：线性O(n) delMin() * k：O(klogn) #### 堆B 随机选取k个元素组织为大顶堆，插入、删除 #### 堆C 两个堆 #### quickSelect 减而治之，经过partition找到一个轴点后，若该轴点大于k，则剪去轴点之后的元素，若小于k，则剪去之前的元素。 ```cpp template <typename T> void quickSelect(Vector<T> & A, Rank k) { for (Rank lo = 0, hi = A.size() - 1; lo < hi;) { Rank i = lo, j = hi; T pivot = A[lo]; while (i < j) { while (i < j && pivot <= A[j]) j--; A[i] = A[j]; while (i < j && A[i] <= pivot) i++; A[j] = A[i]; } A[i] = pivot; if (k <= i) hi = i - 1; if (i <= k) lo = i + 1; } } ``` #### linearSelect 最坏的情况下，也只需要线性时间 把整个向量分成Q份，求每份的中位数，再求这些中位数的中位数，直到平凡情况，使用普通方法，按小于、等于、大于中位数分别放进L、E、G。 新问题的规模都不会超过此前规模的75%  ##### 复杂度 为保证线性，$1/Q + 3/4 < 1$ 可取Q=5 ## 12.3 希尔排序 将整个序列视作一个矩阵，逐列各自排序`w-sorting` 怎么视作一个矩阵呢？列怎么分呢？ **递减增量** - 由粗到细：重排矩阵，使其更窄，再次逐列排序`w-ordered` - 逐步求精：如此往复，直至矩阵变成一列`1-sorting` **步长序列**：由各矩阵宽度构成的**逆序列** <u>不同的步长序列会得到不同的算法</u> ### 几个问题： 1. 既然最终还是要做一次`1-sorting`，那此前的排序有何意义呢？ 2. 如何实现矩阵重排？不用使用二维向量，一维足矣，第i列，$a[i + kw], 0 \le k \lt n/w$ 3. 各列内部如何排序？**输入敏感**，插入排序，取决于输入序列中逆序对的数量 ### 初始希尔序列 ${1, 2, 4, ...}$ 都为偶数，那么每次重组后的每列中都来自同一子串，互不相关  **相邻项要互素才好** 数论？呜呜呜  `h-ordered`：$S[i] \le S[i + h], \space for \space 0 \le i \lt n - h$ 那么1-ordered就是全局有序的。 `h-sorting`：一个`h-ordered`的序列可以由以下步骤得到： 1. 将序列排成h列（逻辑上的，并不创建新的矩阵） 2. 对每列分别排序 **性质**： 1. 此前`g-ordered`序列在经过下一次`h-sorting`后，`g-ordered`仍然保持 2. 如果一个序列既是`g-ordered`，又是`h-ordered`，那么它一定是`(g + h)-ordered`，并且对任意的m, n, 也一定是`(mg + nh)-ordered` 逆序对可能出现的地方为秩小于等于`(g - 1)·(h - 1)`的区间 - 阅读全文 -
数据结构与算法 11. 串 2021-07-28 浏览量 770 暂无评论 [TOC] ## 11.1 ADT ### 术语 $S[0, n)$ 子串：$S.substr(i, k) = S[i, i + k)$ 前缀：$S.prefix(k) = S.substr(0, k) = S[0, k)$ 后缀：$S.suffix(k) = S.substr(n - k, k) = S[n - k, n)$ ## 11.2 串匹配 `grep <pattern> <text>`正则匹配字符串 模式匹配不同的难度： - detection - **location** - counting - enumeration ### 如何评测性能 不能随机采样P和T来评测，因为在随机采样的情况下，匹配成功的概率超低。 随机T，对成功、失败的匹配分别测试 成功：在T中，随机取出长度为m的子串作为P，分析平均复杂度 失败：随机P，统计平均复杂度 ## 11.3 蛮力匹配 版本1 ```cpp int match(char *P, char * T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j = 0; while (j < m && i < n) { if (P[j] == T[i]) {i++; j++} else {i -= j - 1; j = 0} return i - j; } // 若i - j > n - m，则失败，因为已经超过了可能匹配到的最大下界 ``` 版本2 ```cpp int match(char *P, char * T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j; for (i = 0; i < n -m + 1; i++) { for (j = 0; j < m; j++) if (T[i+j] != P[j]) break; if (m <= j) break; } return i; } ``` 复杂度：$O(n * m)$ 缺点： - 不能避免局部匹配 当字母表越大时，蛮力算法的期望复杂度为线性，因为每次只需常数次比较。 ## 11.4 KMP算法：从记忆力到预知力 在当前字符匹配失败时，之前的字符都是匹配成功的，充分利用这一信息 ### next[]表 自匹配 = 快速右移 长度为t的前缀与长度为t的后缀完全匹配。 每次选取这个集合中最大的t，避免回溯。 在当前字符不匹配时，通过查表得到下一次比对开始的地方，之所以可以从这个地方开始，是因为通过这样的移动，前t个位置已经匹配，即在之前已匹配的串中，存在长度为t的相等前后缀。移动的大小为j - t。   统一将next[]表中的第0项置为-1，作为通配哨兵前缀（第0个字符匹配失败，取P[-1]也就是通配符来匹配，接下来，P和T都移到下一位）。 ### 构造next[]表 看next[j]与当前需要比对的字符是否相等，相等则next[j++] = next[j] + 1，否则，取next[next[j]]再比对，直到相等，其中的含义即当前所匹配的相等前后缀子串必然包含在此前已匹配的串中。 ```cpp int* buildNext(char* P) { size_t m = strlen(P), j = 0; int* N = new int[m]; int t = N[0] = -1; while (j < m - 1) if ( 0 > t || P[j] == P[t]) N[++j] = ++t; else t = N[t]; return N; } ``` 为什么可以跳过前i个，是因为以它们开头的字符串都不可能与已P[0, t)开头的字符串匹配，因为匹配到T[i]时，就不匹配了，所以才会有跳过这一步。 复杂度：$O(n)$ ### 缺陷 当模式串中包含连续重复字符时，退化为逐步前进  ```cpp int* buildNext(char* P) { size_t m = strlen(P), j = 0; int* N = new int[m]; int t = N[0] = -1; while (j < m - 1) if ( 0 > t || P[j] == P[t]) j++; t++; N[j] = P[j] != P[t] ? t : N[t]; else t = N[t]; return N; } ``` ## 11.5 BM_BC算法：坏字符 ### 不对称性 利用串匹配的特性：多个字符对多个字符 判断串是否相等与是否不等的成本不同。 ### 前轻后重 优先比对靠后的元素，因为如果靠后的元素失配，那么将模式串移到当前匹配失败字符的下一位 跳过的条件：当前匹配的字符不在模式串内 如果当前匹配失败，并且当前匹配的字符在模式串中，则将模式串中的该字符与其对其  ### 构造bc[] ```cpp int* buildBC(char* P) { int* BC = new int[256]; for (int i = 0; i < 256; i++) BC[i] = -1; for (size_t m = strlen(P), j = 0; j < m; j++) BC[P[j]] = j; return BC; } ``` ### 实现 ```cpp int BMBC(char* P, char* T) { int* BC = buildBC(P); int i = strlen(P) - 1, j = strlen(P) - 1; while (i < strlen(T)) { if (T[i] == P[j]) { i--; j--; } else { if (BC[T[i] == -1) { i += strlen(P) - 1; j = strlen(P) - 1; } else if ((j - BC[T[i]]) < 0) { i += strlen(P) - j; j = strlen(P) - 1; } else { i += strlen(P) - BC[T[i]] - 1; j = strlen(P) - 1; } } } } ``` ### 性能分析 最好：$O(n / m)$ 最坏：$O(n * m)$ 后m-1个字符都匹配，第1个字符不匹配，没有利用好经验。 ## 11.6 BM_GS算法：好后缀 疑问：如果匹配的后缀是重复元素还能省掉中间两趟吗？  记录当前匹配的好后缀，下次移动时，将模式串中的好后缀与其对齐，和KMP有啥本质的区别？ KMP是前后缀，GS可以在模式串中，不一定是前缀 ### 构造 ### BM性能 综合bc和gs 最好：$O(n / m)$ 最差：$O(m + n)$  ## 11.7 Karp-Rabin算法：串即是数 如果能把串变成数，那每次只需要常数次比较 每个有限维的自然数向量，唯一对应于一个自然数。 $<a_1,a_2,...,a_n> ~ p(1)^{1+a_1} \times p(2)^{1+a_2} \times ... \times p(n)^{1+a_n}$ 其中$p(k)$代表第k个素数。  这个数太大了，无法正常存储吧 ### 串亦是数 字符在字母表中的编号  ### 散列 想用指纹（数字）来表示串的话，如果直接转换成对应进制的数字，则位数太高，甚至超过64位（8字节），这样不仅储存不便，比较也不便 **散列压缩** **散列冲突** 两个不同的元素在散列变换后，有可能被映射到同一个散列码，那么再进行严格比对。 **快速指纹计算** 相邻的两个指纹之间，有着某种相关性，理论上可在$O(1)$的时间内，由上一指纹得到下一指纹。 - 阅读全文 -
数据结构与算法 9. 词典 2021-07-27 浏览量 876 暂无评论 [TOC] ## 9.1 散列：原理 一种重要的组织数据并实现算法的思想 循值访问 关键码取值范围大，但利用率低，通过散列对关键码空间进行压缩，保证查找速度的同时，降低存储消耗。 ### 术语 - 桶（bucket）：直接存放或间接指向一个词条 - 桶数组/散列表，容量为M，$N \lt M \ll R$，空间$O(N+M)$，装填因子：$\lambda = N / M$ 根据词条的key直接确定散列表的入口，散列函数：`hash(): key -> &entry`  ### 冲突 经过散列函数后，不同的关键码对应同一个桶单元 好的散列函数可以降低冲突的概率 ## 9.2 散列：散列函数 冲突是难免的  ### 除余法 与2^k除余，效果相当于截取该数的最后k位，前面的n - k位没有影响，故 `key % M = key & (M - 1)` 此种情况下，如果最后k位相同，就会发生冲突 **如果取M为素数，那么冲突概率减少，分布更加均匀**，why？ 又是数论哈哈，蝉的生命周期 ### MAD法 除余法的改进。 **除余法的缺陷**： 1. 不动点：hash(0) = 0 2. 零阶均匀：相邻关键码的散列地址也必相邻，相邻会怎样？视场合 `multiply-add-divide` 取M为素数 ，a > 0, b > 0, a % M ≠ 0，`hash(key) = ((a × key) + b) % M` ### 平方取中 取$key^2$的中间若干位，构成地址，如`hash(123) = 512, `// $key^2 = 123^2 = 15129$ **疑问** 1. 为什么保留居中的数位？<u>越是中间的数位更多的原数位累计得到的，使最终的散列地址尽可能接近</u> 2. 关键码很大时，平方的计算开销不影响吗？甚至上溢 ### 折叠汇总  ### 伪随机数  ### 多项式 key -> hashcode  如果只是简单相加的话，很容易出现冲突 ## 9.3 排解冲突1 ### 多槽位  ### 独立链 改用列表，动态增长  ### 开放定址 独立链式封闭定址（closed addresing），让所有的散列和冲突排解都在一个封闭的空间进行。 每一个词条都有可能被防在任何一个桶中，而不是像之前那样每个词条的位置都是固定的。  ### 线性试探：策略   ### 懒惰删除 按照开放定址策略，先后插入、相互冲突的一组词条，将存放在同一查找链中，若直接删除其中某个词条，查找链会被切断，后续词条丢失--明明存在，却访问不到 懒惰删除的做法就是仅做删除标记，查找链不必续接。 每一个桶单元，都同时属于多个查找链。 ## 9.4 排解冲突2 ### 平方试探 线性试探比较靠近   **定理**：若M是素数，且装填因子小于等于0.5，那么前$\lceil M/2 \rceil$位置一定彼此互异。 ### 双向平方试探  要选合适的素数，不合适的素数会出现前向和逆向都由相同的元素组成的情况。 **4k + 3的素数必然可以保证查找链的前M项互异。** 证明：双平方定理-- ## 9.5 桶/计数排序 复杂度不完全取决于输入的规模，还取决于待排序序列的取值范围，$O(max(n + M))$ 通过每个字母的统计值和累计值，确定其在有序向量中的区间。 - 阅读全文 -
