跳转至

13. 循环不变式和区块链

阅读信息

约 575 个字  2 分钟  本页总访问量：加载中... 次

Class Thirteen

循环不变式

cutoff：当数组中元素数量小于该值时，不再调用递归（防止小数组时效率低）

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int median3(int a[], int left, int right) {
    if (a[left] < a[mid])
        交换左，中；
    if (a[left] < a[right])
        交换左，右；
    if (a[mid] < a[right])
        交换中，右；
    // 此时已达到左 < 中 < 右
    交换中，右-1； // 将pivot 放在端位
    return a[right - 1];
}
Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void Qsort(int a[], int let, int right) {
    if (left + cutoff <= right) {
        for ( ; ; ) {
            while (a[++i] < pivot) ;
            while (a[- -j] > pivot) ;
            if (i < j) swap(i, j);
            else break;
        }
    } else {
        InsertionSort(a);
    }
}

时间复杂度： T(N) = T(i) + T(N-i-1) + cN 最坏：T(N) = T(N-1) + cN, T(N) = O(N^2) 最好：T(N) = 2T(N/2) +cN, T(N) = O(N logN)

问题：给 n 个整数，求第 k 大的数

  1. 从大到小排序，取第 k 个 -> O(N logN)
  2. 找基准元素，将所有元素分为比它小和比它大。如果大的元素有 k-1 个，则第 k 位基准元素；如果小于 k-1 个，从大的元素中找；……小，从小的元素中找 -> O(1+½+¼+…N)=O(N)

大结构的排序问题 和数组排序不同，大结构交换的代价高。用 keyword 代替，根据大结构的性质对 keyword 排序。 关键问题：给定第几个元素放到编号几的位置，怎么重新编排数组？？

证明：通过比较、交换，不可能找到时间复杂度小于 O(N logN)的算法 任何基于比较的算法，都对应一个决策树。 其中，每个节点表示比较语句，分支表示 T 或 F 的情形，叶节点为最终排序结果。 叶节点总数为 n！，则树的高度至少 log N！。 O(log N!) = O(N logN)

不用比较进行排序，时间复杂度可以小于 O(N logN)：如桶排序。

基数排序：分别按个位数、十位数……进行桶排序。（最不重要的数开始） 每次排序时按上一次排序结果遍历。先把一个桶中的数依次遍历完，再遍历下一个桶。

快速排序的需要 O(logN)的空间。（递归需要不断压栈）

稳定性： 插入排序 稳定 堆排序 不稳定（没有依次比较） 分组排序 不稳定 快速排序 不稳定

还可能考：经过几轮后数据序列，判断是什么排序方法

哈希

设计哈希函数，对每个 x 生成 y，且不同 x 得到不同的 y。

区块链应用

目的：让数组不可篡改不可替代 数据组织和管理技术：数据库（增删改查）、区块链（增查） 核心思想：

  1. 把数据放在多个地方（分布式账本技术），多个备份
  2. 把数据前后关联

每隔一定时间记录的所有数据形成一个区块。 将各个区块串联，形成区块链。 怎么将数据串联？用哈希函数。 给每个区块编号，前一个编号通过哈希函数得到下一个编号。 （哈希值可以作为 index，这里作为数据的指纹）

作用：建立可信机制