「算法笔记」(一) 算法初步

本文最后更新于:2022年8月17日 上午

「算法笔记」的读书笔记系列

本笔记来源于「算法笔记 胡凡」第四章 入门篇(2) 算法初步

「算法笔记」(一) 算法初步

1 | 排序

这里算法笔记只讲了选择排序和插入排序, 其中选择排序是不稳定的排序, 插入排序是稳定的排序, 下面给出多个常见排序的复杂度和稳定性分析:

引自

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 每次选出[i, n]中最小的元素, 不稳定
void selectSort(vector<int>& vec) {
int n = vec.size();
for (int i = 0; i < n; ++i) {
int k = i;
for (int j = i; j < n; ++j) {
if (vec[j] < vec[k]) {
k = j;
}
}
swap(vec[k], vec[i]);
}
}

直接插入排序

直接插入排序示意图

1
2
3
4
5
6
7
8
9
10
11
12
void insertSort(vector<int>& vec) {
int n = vec.size();
for (int i = 1; i < n; ++i) {
int temp = vec[i], j = i;
// 找到插入的位置
while (j > 0 && temp < vec[j - 1]) {
vec[j] = vec[j - 1];
j--;
}
vec[j] = temp;
}
}

归并, 快排, 堆排

我的算法期末复习博客中包含了相关介绍(基于「算法 第四版」)

2 | 散列 (hash)

散列(hash, 哈希): 将元素通过一个函数转换为整数, 使得该整数可以尽量唯一地代表这个元素

元素key —> 整数H(key)

常用的hash算法:

  • 除留余数法H(key) = key % mod

  • 直接定址法H(key) = key

  • 平方取中法 (少见) (取key^2的若干中间位作为hash值)

常用的解决冲突算法:

H(key1) == H(key2)时, 产生冲突, 需要解决冲突, 下面是常用方法:

  • 线性探查法 (Linear Probing)

H(key)产生冲突时H(key)++直到没有冲突

  • 平方探查法(Quadratic Probing)

H(key) +- k^2其中k从1到n取值

  • 链地址法(拉链法)

把所有相同的key, 连接成一条单链表

字符串哈希

将A-Z的26个字母对应到0-25, 从而将字符串用26进制表示, 剩余处理同上

哈希表的大小需要为$26^{len}-1$, len为字符串长度

1
2
3
4
5
6
7
int hashFunc(char S[], int len) {
int id = 0;
for (int i = 0; i < len; ++i) {
id = id * 26 + (S[i] - 'A'); // 转换为26进制表示
}
return id;
}

如果出现小写字母, 则变为52进制

出现数字, 变为62进制

3 | 二分

递归和贪心比较简单, 这里略过

经典的二分查找: 如何在一个严格递增序列A中找出给定的数x

二分查找代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 二分法在有序vec中寻找x, 返回值为x的下标, 如果没找到返回-1
int binarySearch(vector<int>& vec, int x) {
int left = 0, right = vec.size() - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1); // 防止溢出
if (vec[mid] == x) return mid;
else if (vec[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}

upper_bound 和lower_bound

关于lower_boundupper_bound函数的实现:

lower_bound用于寻找第一个大于等于x的元素

upper_bound用于寻找第一个大于x的元素

lower_bound的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 第一个大于等于x的元素下标
int lowerBound(vector<int>& vec, int x) {
int left = 0;
int right = vec.size(); //加入x比所有元素都大, 应当返回vec.size()
int mid;
while (left < right) {
mid = left + ((right - left) >> 1);
if (vec[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

upper_bound的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 第一个大于x的元素下标
int upperBound(vector<int> &vec, int x) {
int left = 0, right = vec.size();
int mid;
while (left < right) {
mid = left + ((right - left) >> 1);
if (vec[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

解决这类问题(寻找有序序列第一个满足某条件元素的位置)题目的写法:

1
2
3
4
5
6
7
8
9
10
11
12
int solve (int left, int right) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (条件成立) { // 条件成立, 第一个满足条件的元素位置 <= mid
right = mid;
} else { // 条件不成立, 第一个满足条件的元素位置 > mid
left = mid + 1;
}
}
return left;
}

快速幂

基本问题:

给定三个整数a, b, m, 求$\mathrm{a}^{\mathrm{b}}\%\mathrm{m}$

直接暴力的写法:

1
2
3
4
5
6
7
llpow(long long a, long long b, long long m) {
long long ans = 1;
for (int i = 0; i < b; ++i) {
ans = ans * a % m;
}
return ans;
}

时间复杂度O(b), 当b很大时(>$10^8$), 暴力的方法行不通

快速幂的方法基于如下两个事实:

  1. 如果b是奇数, 那么$\mathrm{a}^{\mathrm{b}}=\mathrm{a}\times \mathrm{a}^{\mathrm{b}-1}$
  2. 如果b是偶数, 那么$\mathrm{a}^{\mathrm{b}}=\mathrm{a}^{\frac{\mathrm{b}}{2}}\times \mathrm{a}^{\frac{\mathrm{b}}{2}}$

递归写法

显然b为奇数的情况可以转换为b为偶数的情况, 基于二分的思想则得到快速幂的O(logb)递归写法:

1
2
3
4
5
6
7
8
9
long long binaryPow(long long a, long long b, long long m) {
if (b == 0) return 1;
if (b & 1) return a * binaryPow(a, b - 1, m) % m; // b为奇数
else { // b为偶数
// 先计算mul = binaryPow而不要使用binaryPow * binaryPow的形式, 否则时间复杂度将变为O(b)
long long mul = binaryPow(a, b / 2, m);
return mul * mul % m;
}
}

迭代写法

比如b = 13可以写为1101, 则$13=2^3+2^2+2^0$, 即$\mathrm{a}^{13}=\mathrm{a}^{2^3}\times \mathrm{a}^{2^2}\times \mathrm{a}^{2^0}$

所以得到迭代写法如下:

  1. 初始ans = 1
  2. 判断b(二进制)的末尾是否为1, 如果是, ans *= a
  3. a*=a(平方)并将b右移一位
  4. b > 0则返回步骤2
1
2
3
4
5
6
7
8
9
10
11
binaryPow(long long a, long long b, long long m) {
long long ans = 1;
while (b > 0) {
if (b & 1) {
ans = ans * a % m;
}
a = a * a % m;
b >>= 1;
}
return ans;
}

迭代与递归的效率对比差不多, 但是迭代更好理解(


「算法笔记」(一) 算法初步
https://blog.roccoshi.top/posts/19513/
作者
RoccoShi
发布于
2021年1月15日
许可协议