《我的第一本算法书》阅读学习笔记

https://www.ituring.com.cn/book/2464

注：这本书讲解比较简单和直观，并没有深入代码层面，排序部分的代码来源菜鸟教程

一、数据结构

1.链表

基本链表、循环链表、双向链表

在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内

在链表中，数据的添加和删除较为方便，访问比较耗费时间(因为数据都是分散存储的)

在这里，我们把链表中的数据量记成n。访问数据时，我们需要从链表头部开始查找（线性查找），如果目标数据在链表最后的话，需要的时间就是O(n)。另外，添加数据只需要更改两个指针的指向，所以耗费的时间与n无关。如果已经到达了添加数据的位置，那么添加操作只需花费O(1)的时间。删除操作同理

2.数组

操作时间在内存的连续空间内

在数组中，访问数据十分简单，而添加和删除数据比较耗工夫

由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫作“随机访问”）

这里讲解一下对数组操作所花费的运行时间。假设数组中有n个数据，由于访问数据时使用的是随机访问（通过下标可计算出内存地址），所以需要的运行时间仅为恒定的O(1)。但另一方面，想要向数组中添加新数据时，必须把目标位置后面的数据一个个移开。所以，如果在数组头部添加数据，就需要O(n)的时间。删除操作同理

在链表和数组中，数据都是线性地排成一列。在链表中访问数据较为复杂，添加和删除数据较为简单；而在数组中访问数据比较简单，添加和删除数据却比较复杂

\	访问	添加	删除
链表	慢	快	快
数组	快	慢	慢

3.栈

栈也是一种数据呈线性排列的数据结构，先进后出，后进先出(Last In First Out /LIFO)

4.队列

队列中的数据也呈线性排列，虽然与栈有些相似，但队列中添加和删除数据的操作分别是在两端进行的(类似排队)，先进先出(First In First Out/ FIFO)

5.哈希表

哈希表存储的是由键（key）和值（value）组成的数据

一般来说，我们可以把键当成数据的标识符，把值当成数据的内容

在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储(链地址法)。这样一来，不管数据量为多少，我们都能够灵活应对。如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间非常重要

6.堆

堆是一种图的树形结构(类似于完全二叉树)，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中，堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右

如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便

在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。

添加数据
往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端，如果父结点大于子结点，则不符合上文提到的规则，因此需要交换父子结点的位置，重复这样的操作直到数据都符合规则，不再需要交换为止
删除数据
从堆中取出数据时，取出的是最上面的数据，这样，堆中就能始终保持最上面的数据最小

取出数据后，将最后的数据移动到最顶端，如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换，重复这个操作直到数据都符合规则，不再需要交换为止

堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O(1)。另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log2n，那么重构树的时间复杂度便为O(logn)。添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是O(logn)

7.二叉查找树

也采用图的树形结构，数据存储于二叉查找树的各个结点中

性质：

1.每个结点的值均大于其左子树上任意一个结点的值

2.每个结点的值均小于其右子树上任意一个结点的值

二叉查找树的最小结点要从顶端开始，往其左下的末端寻找；二叉查找树的最大结点要从顶端开始，往其右下的末端寻找

添加数据
从二叉查找树的顶端结点开始寻找添加数字的位置。将想要添加的1与该结点中的值进行比较，小于它则往左移，大于它则往右移
删除数据
1.若需要删除的结点没有子结点，则直接删除即可
2.若需要删除的结点只有一个子结点，则先删除目标结点再把子结点移到被删除结点的位置即可
3.若需要删除的结点有两个子结点，则先删除目标结点，再在被删除结点的左子树中寻找最大结点，再将最大结点移到被删除结点的位置上，如果需要移动的结点（此处为4）还有子结点，就递归执行前面的操作
查找数据
从二叉查找树的顶端结点开始往下查找。和添加数据时一样，把需要查找的数据和结点中的值进行比较，小于该结点的值则往左移，大于则往右移

我们可以把二叉查找树当作是二分查找算法思想的树形结构体现。因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移动了。

比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是$log_2^n$。因此，时间复杂度为$O(logn)$。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了$O(n)$

二、排序算法

排序就是将输入的数字按照从小到大的顺序进行排列

1.冒泡排序

个人理解：从左到右或从右到左逐渐比较相邻两个数字，再根据结果交换位置

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序“

在冒泡排序中，第1轮需要比较n-1次，第2轮需要比较n-2次……第n-1轮需要比较1次。因此，总的比较次数为$(n-1)+(n-2)+…+1\approx \frac{n^2}{2}$。这个比较次数恒定为该数值，和输入数据的排列顺序无关。不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度为$O(n^2)$

// 冒泡排序关键代码
for(int i = 0;i < len - 1;i++)
{
    for(int j = 0; j < len - 1 - i; j++)
    {
        if(nums[j] > nums[j + 1])
        {
            int temp = nums[j + 1];
            nums[j + 1] = nums[j];
            nums[j] = temp;
        }
    }
}

2.选择排序

个人理解：比较待排序数据并将其中最小值放到最左边，然后再在去掉该数据后的剩余数据重复上述操作

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找

选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是$(n-1)+(n-2)+…+1\approx \frac{n^2}{2}$次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为$O(n^2)$

// 选择排序关键代码
for(int i = 0;i < len - 1;i++)
{
    int min = i;	// 最小值的下标
    for(int j = i + 1;j < len;j++)
    {
        if(nums[j] < nums[min])
        {
            min = j;	// 更新最小值下标
        }
    }
    int temp = nums[min];
    nums[min] = nums[i];
    nums[i] = temp;
}

3.插入排序

插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上

在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体来说，就是第k轮需要比较k-1次。因此，在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度和冒泡排序的一样，都为$O(n^2)$。和前面讲的排序算法一样，输入数据按从大到小的顺序排列时就是最糟糕的情况

// 插入排序关键代码
for(int i = 0;i < len;i++)
{
    int key = nums[i];
    int j = i - 1;
    while((j >= 0) && (key < nums[j]))
    {
        nums[j + 1] = nums[j];	// 排好序的数据往后移，为插入数据腾出位置
        j--;
    }
    nums[j + 1] = key;	// 空余位置插入数据 因为while里存在j--所以需要外面j+1
}

4.堆排序

堆排序一开始需要将n个数据存进堆里，所需时间为$O(nlogn)$。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于$log_2n$，所以插入1个数据所需要的时间为$O(logn)$。每轮取出最大的数据并重构堆所需要的时间为$O(logn)$。由于总共有n轮，所以重构后排序的时间也是$O(nlogn)$。因此，整体来看堆排序的时间复杂度为$O(nlogn)$。这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间$O(n^2)$都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难

void max_heapify(int arr[], int start, int end)
{
    // 初始化父结点和子结点索引
    int dad = start;
    int son = dad * 2 + 1;
    // 子结点在数组中
    while(son <= end)
    {
        if(son + 1 <= end && arr[son] < arr[son + 1])	// 选择最大子结点
        {
            son++;
        }
        if(arr[dad] > arr[son])	// 父结点大于子结点,无需调整堆
        {
            return;
        }
        else	// 否则交换父结点和子结点再继续比较子结点和孙结点
        {
            swap(arr[dad],arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }    
    }
}

void heap_sort(int arr[], int len)
{
    // 初始化 i从最后一个父结点开始调整
    for(int i = len/2 - 1;i >= 0;i--)
    {
        max_heapify(arr, i, len - 1);
    }
    // 交换第一个元素和已经排好的元素前一位(也即未排序的最后一个元素), 再重新调整，直到排序完毕
    for(int i = len - 1;i > 0;i--)
    {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main()
{
    int nums[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(nums) / sizeof(*nums);
    heap_sort(nums, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

5.归并排序

归并排序算法(分治法)会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。看一下上面的图便能得知，无论哪一行都是n个数据，所以每行的运行时间都为$O(n)$。而将长度为n的序列对半分割直到只有一个数据为止时，可以分成$log_2n$行，因此，总共有$log_2n$行。也就是说，总的运行时间为$O(nlogn)$，这与堆排序相同

// 迭代版本
template<typename T>
void merge_sort(T arr[], int len)
{
    T *a = arr;
    T *b = new T[len];
    for(int seg = 1; seg < len; sge += seg)
    {
        for(int start = 0; start < len; start += seg + seg)
        {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while(start1 < end1 && start2 < end2)
            {
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            }
            while(start1 < end1)
            {
                b[k++] = a[start1++];
            }
            while(start2 < end2)
            {
                b[k++] = a[start2++];
            }
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if(a != arr)
    {
        for(int i = 0;i < len; i++)
        {
            b[i] = a[i];
        }
        b = a;
    }
    delete[] b;
}

// 递归版本
void Merge(vector<int> &arr, int front, int mid, int end)
{
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(arr.begin() + front, arr.begin() + mid + 1);
    vector<int> RightSubArray(arr.begin() + mid + 1, arr.begin() + end + 1);
    int idxLeft =0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for(int i = front; i <= end; i++)
    {
        if(LeftSubArray[idxLeft] < RightSubArray[idxRight])
        {
            arr[i] = LeftSubArray[idxLeft];
            idxLeft++;
        }
        else
        {
            arr[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(Vector<int> &arr, int front, int end)
{
    if(front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(arr, front, mid);
    MergeSort(arr, mid + 1, end);
    Merge(arr, front, mid, end);
}

6.快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式：

[比基准值小的数] 基准值 [比基准值大的数]

接着，对两个[ ]中的数据进行排序之后，整体的排序便完成了

快速排序是一种“分治法”。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。子问题，也就是子序列完成排序后，再像一开始说明的那样，把他们合并成一个序列，那么对原始序列的排序也就完成了。不过，解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成

分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序的运行时间和归并排序的一样，都为$O(nlogn)$。和归并排序类似，将序列对半分割$log_2n$次之后，子序列里便只剩下一个数据，这时子序列的排序也就完成了

如果运气不好，每次都选择最小值作为基准值，那么每次都需要把其他数据移到基准值的右边，递归执行n行，运行时间也就成了$O(n^2)$。这就相当于每次都选出最小值并把它移到了最左边，这个操作也就和选择排序一样了。此外，如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间为$O(nlogn)$

// 迭代版本
struct Range {
    int start, end;
    Range(int s = 0, int e = 0) {
        start = s, end = e;
    }
};
template <typename T>
void quick_sort(T arr[], const int len) {
    if (len <= 0)
        return;
    // r[]模拟堆疊,p为数量,r[p++]为push,r[--p]为pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = Range(0, len - 1);
    while (p)
    {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right) left++;
            while (arr[right] >= mid && left < right) right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}

// 递归版本
template<typename T>
void quick_sort_recursive(T arr[], int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right) left++;
        while (arr[right] >= mid && left < right) right--;
        std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}

template<typename T>
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

三、数组的查找

1.线性查找

线性查找是一种在数组中查找数据的算法。与二分查找不同，即便数据没有按顺序存储，也可以应用线性查找。线性查找的操作很简单，只要在数组中从头开始依次往下查找即可

线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为n，线性查找的时间复杂度便为$O(n)$

2.二分查找

二分查找也是一种在数组中查找数据的算法。和线性查找不同，它只能查找已经排好序的数据。二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。因此，比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据，或得出目标数据不存在的结论

数据量为n的数组，将其长度减半$log_2n$次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作$log_2n$次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为$O(logn)$

四、图的搜索

图：与图论中的图相似

图的搜索指的就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种

1.广度优先搜索

广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快

搜索的候补顶点采用先入先出的方式管理，适合使用队列这个数据结构

2.深度优先搜索

深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径

搜索的候补顶点采用后入先出方式管理，适合使用栈这个数据结构

3.贝尔曼-福特（Bellman-Ford）算法

这是一种在图中求解最短路径问题的算法，基本思路是不断更新顶点权重直至不能更新为止

将图的顶点数设为n、边数设为m，我们来思考一下贝尔曼-福特算法的时间复杂度是多少。该算法经过n轮更新操作后就会停止，而在每轮更新操作中都需要对各个边进行1次确认，因此1轮更新所花费的时间就是$O(nm)$，整体的时间复杂度就是$O(nm)$

4.狄克斯特拉（Dijkstra）算法

比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，狄克斯特拉算法多了一步选择顶点的操作，这使得它在求最短路径上更为高效。

将图的顶点数设为n、边数设为m，那么如果事先不进行任何处理，该算法的时间复杂度就是$O(n^2)$。不过，如果对数据结构进行优化，那么时间复杂度就会变为$O(m+nlogn)$

如果闭环中有负数权重，就不存在最短路径。贝尔曼-福特算法可以直接认定不存在最短路径，但在狄克斯特拉算法中，即便不存在最短路径，它也会算出一个错误的最短路径出来。因此，有负数权重时不能使用狄克斯特拉算法。总的来说，就是不存在负数权重时，更适合使用效率较高的狄克斯特拉算法，而存在负数权重时，即便较为耗时，也应该使用可以得到正确答案的贝尔曼-福特算法。

5.A*（A-Star）算法

该算法由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A*就会预先估算一个值，并利用这个值来省去一些无用的计算

如果我们能得到一些启发信息，即各个顶点到终点的大致距离（这个距离不需是准确的值）我们就能使用A算法。当然，有时这类信息是完全无法估算的，这时就不能使用A算法。距离估算值越接近当前顶点到终点的实际值，A*算法的搜索效率也就越高；反过来，如果距离估算值与实际值相差较大，那么该算法的效率可能会比狄克斯特拉算法的还要低。如果差距再大一些，甚至可能无法得到正确答案。不过，当距离估算值小于实际距离时，是一定可以得到正确答案的（只是如果没有设定合适的距离估算值，效率会变差）

五、安全算法

传输数据时的四个问题及解决的安全技术：

窃听->加密

假冒->消息认证码/数字签名

篡改->消息认证码/数字签名

事后否认->数字签名

1.加密

加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程

解密就是通过密钥进行数值计算，把密文恢复成原本数据的过程

像这样，将数据变成第三者的计算机无法理解的形式，然后再将其恢复成原本数据的一系列操作就是加密技术。

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景

哈希函数特征：

输出的哈希值数据长度不变(不管输入数据是什么，哈希值长度仍然相同)

输入数据相同，则输出哈希值也必定相同(在相同算法情况下)

即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似

即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”

不可能从哈希值反向推算出原本的数据

求解哈希值的计算相对容易

哈希函数的算法中具有代表性的是MD5、SHA-1和SHA-2等。其中SHA-2是现在应用较为广泛的一个，而MD5和SHA-1存在安全隐患，不推荐使用

共享密钥加密

加密数据的方法可以分为两种：加密和解密都使用相同密钥的“共享密钥加密”和分别使用不同密钥的“公开密钥加密”

共享密钥加密是加密和解密都使用相同密钥的一种加密方式。由于使用的密钥相同，所以这种算法也被称为“对称加密”。实现共享密钥加密的算法有凯撒密码、AES、DES、动态口令等，其中AES的应用最为广泛

公开密钥加密

由于公开密钥加密使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”

实现公开密钥加密的算法有RAS算法、椭圆曲线加密算法等，其中使用最为广泛的是RSA算法

通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击”（man-in-the-middle attack）

混合加密

共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密

迪菲-赫尔曼密钥交换

迪菲-赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换

使用迪菲-赫尔曼密钥交换，通信双方仅通过交换一些公开信息就可以实现密钥交换。但实际上，双方并没有交换密钥，而是生成了密钥。因此，该方法又被叫作“迪菲-赫尔曼密钥协议”

消息认证码MAC（Message Authentication Code）

消息认证码可以实现“认证”和“检测篡改”这两个功能

可以把MAC想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有HMAC、OMAC、CMAC等。目前，HMAC的应用最为广泛

使用MAC时，生成的一方和检测的一方持有同样的密钥，所以不能确定MAC由哪方生成。这个问题可以用下一节将会讲到的“数字签名”来解决

数字签名

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生

数字签名的生成使用的是公开密钥加密

在公开密钥加密中，用公开密钥加密的数据都可以用私有密钥还原。而本节讲解的数字签名利用的是用私有密钥加密的数据，用公开密钥解密后就能还原这一性质。也就是说，即使密钥的使用顺序不同，运行结果也都是一样的。并不是所有的公开密钥加密都具有这个性质，不过RSA加密算法是可以的。能够用A的公开密钥解密的密文，必定是由A生成的。因此，我们可以利用这个结论来确认消息的发送者是否为A，消息是否被人篡改

公开密钥加密的加密和解密都比较耗时。为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用

数字证书

六、聚类及其他算法

聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。

如何定义“相似”：定义数据间的差距(根据数据类型不同，定义该数据是否“相似”的标准也不同。具体来说，就是要对两个数据之间的“差距”进行定义)

1.k-means算法

k-means算法是聚类算法中的一种，它可以根据事先给定的簇的数量进行聚类

k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，这一点已经在数学层面上得到证明

2.欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数

求解两个数的最大公约数通常做法是先对两个数字因式分解，找出共同的素数，然后求出最大公约数（GCD）

3.素性测试

素性测试是判断一个自然数是否为素数的测试。素数（prime number）就是只能被1和其自身整除，且大于1的自然数

费马小定理：
$$
p = 素数 \
n < p \
n^p\ mod\ p = n
$$
如果p是素数，那么所有比p小的数n都满足$n^p\ mod\ p = n$这个条件。但反过来，即使所有n都满足条件，p也有可能不是素数。因为在极低概率下会出现所有n都满足条件的合数（非素数的自然数，叫做“卡迈克尔数”（Carmichael numbers），也叫“绝对伪素数”）如：561 1105 1729 2465 2821 6601 8911 10585 15841…