数据结构与算法基础(青岛大学-王卓)(9)

2023-10-27 22:30

本文主要是介绍数据结构与算法基础(青岛大学-王卓)(9),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


终于迎来了最后一部分(排序)了,整个王卓老师的数据结构就算是一刷完成了,但是也才是数据结构的开始而已,以后继续与诸位共勉 😃 (PS.记得继续守护家人们的健康当然还有你自己的)。用三根美味的烤香肠开始吧。。。


文章目录

    • 排序
      • 基本概念和排序方法概述
        • 排序
        • 排序方法概述
        • 按排序依据原则
      • 插入排序
        • 直接插入排序
          • 插入法(临时空间)
          • 插入法(哨兵): 就是将临时空间替换成预留的0号位置
          • 算法
          • 性能分析
        • 折半插入排序
          • 算法
          • 算法分析
        • 希尔排序(Donald.L.Shell)
          • 基本思想
          • 算法效率
      • 交换排序
        • 冒泡排序
          • 算法
          • 改进算法(添加交换标志):
          • 效率分析
          • 冒泡排序算法总结
        • 快速排序
          • 基本思想
          • 具体实现
          • 算法
          • 性能分析
      • 选择排序
        • 简单选择排序
          • 基本操作
          • 算法
          • 时间复杂度
        • 堆排序
          • 堆的定义
          • 堆排序定义
      • 归并排序
        • 基本思想
        • 算法
        • 效率
      • 基数排序
        • 基本思想
        • 排序方法
        • 性能分析
      • 各种排序方法比较
        • 时间性能
        • 空间性能
        • 排序方法的稳定性能
        • 关于"排序方法的时间复杂度的下限"
    • 这是条美丽的分割线

排序

基本概念和排序方法概述

排序

将无序序列排成一个有序序列(由小到大或由大到小)的运算。

如果参加排序的数据结点包含多个数据域,那么排序往往是针对其中某个域而言

排序方法概述
  • 存储介质:

    • 内部排序:数据量不大、数据在内存,无需内外存交换数据
    • 外部排序:数据量较大、数据在外存(文件排序)(外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多)
  • 比较器个数:

    • 串行排序:单处理机(同一时刻比较一对元素)
    • 并行排序:多处理机(同一时刻比较多对元素)
  • 主要操作:

    • 比较排序:用比较的方法, 包含插入排序、交换排序、选择排序、归并排序
    • 基数排序:不比较元素的大小,仅仅根据元素本身的取值确定其有序位置。
  • 辅助空间:

    • 原地排序:辅助空间用量为 O(1) 的排序方法。(所占的辅助存储空间与参加排序的数据量大小无关)
    • 非原地排序:辅助空间用量超过 O(1) 的排序方法。
  • 稳定性:

    • 稳定排序:能够使田可数值相等的元素,排序以后相对次序不变。
    • 非稳定性排序:不是稳定排序的方法。
    • 排序的稳定性只对结构类型数据排序有意义。
  • 自然性:

    • 自然排序:输入数据越有序,排序的速度越快的排序方法。
    • 非自然排序:不是自然排序的方法。
按排序依据原则

插入排序:直接插入排序、折半插入排序、希尔排序

交换排序:冒泡排序、快速排序

选择排序:简单选择排序、堆排序

归并排序: 2 一路归并排序

基数排序

按排序所需工作量

简单的排序方法: T(n)=O(n2)

基数排序: T(n)=O(d.n)

先进的排序方法: T(n)=O(nlogn)

存储结构 - 以顺序表记录序列

在这里插入图片描述

插入排序

基本操作:有序插入

  • 在有序序列中插入一个元素,保持序列有序,有序长度不断增加。

  • 起初, a[0] 是长度为 1 的子序列。然后,逐一将 a[1]至 a[n-1] 插入到有序子序列中。

  • 在插入 a[i]前,数组 a 的前半段( a[0] ~ a[i-1]) 是有序段,后半段( a[i] ~a[n-1]) 是停留于输入次序的无序段

  • 插入 a[i]使 a[0] ~ a[i-1] 保持有序,也就是要为 a[i] 找到有序位置 j( 0 <= j <= i ),将 a[i] 插入在 a[j] 的位置上。

  • 插入位置:中间,前面,后面

插入排序种类:直接插入排序、折半插入排序、希尔排序
在这里插入图片描述

直接插入排序

用顺序查找法查找插入位置

插入法(临时空间)

在这里插入图片描述
在这里插入图片描述

插入法(哨兵): 就是将临时空间替换成预留的0号位置

在这里插入图片描述

另外当我们插入i=6号位置的时候,如果i的值比前面一位(5号位)大,因为前面已经是有序了,所以i一定比前面所有元素都大,那就没有比较再赋值到哨兵位置比较了。
在这里插入图片描述

算法
void InsertSort(Sqlist &L) {int i,j;for (i=2; i<=L.length; ++i) {if (L.r[i].key < L.r[i-1].key) {  //若需插入元素比前面元素大就不用比较,反之要将L.r[i]插入有序子表排序L.r[0] = L.r[i];  // 复制为哨兵for (j=i-1; L.r[0].key<L.r[j].key; --j) {L.r[j+1] = L.r[j]; //记录后移}L.r[j+1] = L.r[0]; //插入到正确位置}}
}
性能分析

实现排序的基本操作有两个:1. "比较"序列中两个关键字的大小;2. "移动"记录。
在这里插入图片描述
在这里插入图片描述在这里插入图片描述

时间复杂度结论

  • 原始数据越接近有序,排序速度越快

  • 最坏情况下(输入数据是逆有序的)Tw(n)=O(n2)

  • 平均情况下,耗时差不多是最坏情况的一半 Te(n)=O(n2)

  • 要提高查找速度

    • 减少元素的比较次数

    • 减少元素的移动次数

折半插入排序

查找位置时采用折半查找法

在这里插入图片描述

算法
void BInsertSort(SqList &L) {for (i=2; i<=L.length; ++i) { //依次插入第2~n个元素L.r[0]=L.r[i];  //待插入元素放入哨兵位置low=1; high=i-1; //二分法查找插入位置while (low<=high) {mid=(low+high)/2;if (L.r[0].key<L.r[mid].key) {high=mid-1;} else {low=mid+1;}} // 循环结束,high+1为插入位置for (j=i-1; j>=high+1; --j;) {  //将(high+1)~(i-1)的元素后移,空出(high+1)位置L.r[j+1]=L.r[j];   }L.r[high+1]=L.r[0];  //正确位置插入元素i}
}
算法分析
  • 折半插入排序的平均性能 > 直接插入排序

  • 它所需要的关键码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第 i 个对象时,需要经过 ⌊ l o g 2 i ⌋ \lfloor log~2~i\rfloor log 2 i+1 次关键码比较,才能确定它应插入的位置,

    • 当 n 较大时,总关键码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况(直接插入排序仅1次)要差;
    • 在对象的初始排列已经按关腱码排好序或接近有序时,直接插入排序比折半插入排序执行的关键码比较次数要少;
  • 折半插入排序的对象移动次数与直接插入排序相同,依赖于对象初始排列

    • 减少了比较次数,但没有减少移动次数
    • 平均性能优于直接插入排序
  • 时间复杂度为 O(n2)

  • 空间复杂度为 O(1)

  • 是一种稳定的排序方法

希尔排序(Donald.L.Shell)
基本思想

先将整待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

希尔排序算法,特点:1)缩小增量 2)多遍插入排序
在这里插入图片描述

排序思路:

  1. 定义增量序列 Dk :DM>DM-1>…>D1=1, 刚才的例子中: D3 = 5 , D2 = 3 , D1 = 1
  2. 对每个 Dk 进行 "Dk-间隔"插入排序 (k=M, M-1,1)

特点:

  • 一次移动,移动位置较大,跳跃式地接近排序后的最终位置
  • 最后一次只需要少量移动
  • 增量序列必须是递减的,最后一个必须是 1
  • 增量序列应该是互质的

算法:

void ShellSort(SqList &L, int dlta[], int t) {// dlta[t]存放步长dk的值,按增量序列dlta[0..t-1]对顺序表L做希尔排序for (k=0; k<t; ++k) { //t为多少趟ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序}
}void ShellInsert(SqList &L, int dk) {//对顺序表L进行一趟增量为dk的Shell排序,dk为步长因子for (i=dk+1; i<=L.length; ++i) {if (L.r[i].key<L.r[i-dk].key) {L.r[0]=L.r[i];for (j=i-dk; j>0 && (L.r[0].key<L.r[j].key); j=j-dk) {L.r[j+dk] = L.r[j];}L.r[j+dk] = L.r[0];}}
}
算法效率

希尔排序算法效率与增量序列的取值有关
在这里插入图片描述在这里插入图片描述

希尔排序法是一种不稳定的排序算法。

在这里插入图片描述

Note: 如何选择最佳 d 序列,目前尚未解决, 最后一个增量值必须为1,没有除了1之外的公因子,不宜在链式存储结构上实现。

交换排序

冒泡排序

基于简单交换思想:每趟不断将记录两两比较,并按"前小后大"规则交换

在这里插入图片描述

总结:

  • n 个记录,总共需要 n-1 趟
  • 第 m 趟需要比较 n - m 次
算法
//冒泡排序算法
void Bubble_Sort(SqList &L) {int m,i; RedType x; // 交换时所需临时空间for (m=1; m<=n-1; m++) { //总共m=n-1趟for (i=1; i<=n-m; i++) { //每趟比较n-m趟if (L.r[i].key > L.r[i+1].key) { //发生逆序,交换位置x = L.r[i];L.r[i] = L.r[i+1];L.r[i+1] = x;}}}
}

优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素。

如何提高效率:一旦某一趟比较时不出现记录交换,说明已排好序了就可以结束本算法。

在这里插入图片描述

改进算法(添加交换标志):
//冒泡排序算法改进版(添加是否发生交换的标记)
void Bubble_Sort(SqList &L) {int m,i,flag=1; RedType x; // flag作为是否有交换的标记for (m=1; (flag=1) && (m<=n-1); m++) { //总共m=n-1趟flag=0; // 初始化为0,即没有交换for (i=1; i<=n-m; i++) { //每趟比较n-m趟if (L.r[i].key > L.r[i+1].key) { //发生逆序,交换位置flag=1;  //发生交换后flag做标记,这样可以进行下一轮,如果没交换则为0,上层趟数循环结束x = L.r[i];L.r[i] = L.r[i+1];L.r[i+1] = x;}}}
}
效率分析

在这里插入图片描述

冒泡排序算法总结
  • 最好时间复杂度是 O(n)
  • 最坏时间复杂度为 O(n2)
  • 平均时间复杂度为 O(n2)
  • 冒泡排序算法中增加一个辅助空间 temp ,辅助空间为 S(n)=O(1)
  • 冒泡排序是稳定的
快速排序

– 改进的交换排序

基本思想
  • 任取一个元素(如:第一个)为中心(pivot)
  • 所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表
  • 对各子表重新选择中心元素并依此规则调整(递归思想),直到每个子表的元素只剩一个
  • 最终达到整个序列有序

在这里插入图片描述

具体实现

选定一个中间数作为参考,所有元素与之比较,小的调到其左边(从左往右放),大的调到其右边(从右往左放)。

(枢轴)中间数:可以是第一个数、最后一个数、最中间一个数、任选一个数等

在这里插入图片描述

==> 上面的方法在元素量很大的情况下会非常费空间,因为需要一个额外的表空间来存放数据。

改进:直接利用0号空间存放中间数

  1. 每一趟的子表的形成是采用从两头向中间交替式逼近法
  2. 由 于每趟中对各子表的操作都相似,可采用递归算法

在这里插入图片描述

算法
void main() {QSort(L,1,L.length);
}void QSort(SqList &L, int low, int high) { //对顺序表L快速排序if (low < high) {  //长度>1pivotloc=Partition(L, low, high); //将L.r[low...high]一分为二,pivotloc为枢轴元素排好序的位置QSort(L, low, pivotloc-1); //对低子表递归排序QSort(L, pivotloc+1, high); //对高子表递归排序}
}int Partition(SqList &L, int low, int high) {L.r[0]=L.r[low]; //放置pivot到0号位置pivotkey=L.r[low].key; //方便比较计算中枢的值while (low < high) {while ((low < high)&&(pivotkey <= L.r[high].key)) --high; //先找high位的值放到空的low去L.r[low]=L.r[high];while ((low < high)&&(pivotkey >= L.r[low].key)) ++low; //再找low位的值放到空的high去L.r[high]=L.r[low];}L.r[low]=L.r[0]; // 所有找完后low=high,将此位置返回给pivotlocreturn low; 
}
性能分析
  • 时间复杂度:可以证明,平均计算时间O(nlog2n)

    • Qsort( ): O(log2n)
    • Partition( ): O(n)
  • 实验结果表明:就平均计算时间而言,快速排序是我们所讨论的所有内排序方法中最好的一个.

  • 空间复杂度:快速排序不是原地排序

    • 由于程序中使用了递归,需要递归调用栈的支持,而栈的长度取决于递归调用的深度。(即使不用递归,也需要用用户栈)。
    • 在平均情况下:需要 O(logn)的栈空间。
    • 最坏情况下:栈空间可达 O(n)。
  • 快速排序是一种不稳定的排序方法
    在这里插入图片描述

  • 快速排序不适于对原本有序或基本有序的记录序列进行排序(有序的记录在一次划分之后得到的其中一个子序列的长度会为0,这个时候就退化成没有改进措施的冒泡排序)。

    • 试对( 90 , 85 , 79 , 74 , 68 , 50 , 46 )进行快速排序的划分
    • (子序列0) 90(pivotloc) 85, 79, 74, 68, 50, 46(子序列1)
  • 划分元素的选取是影响时间性能的关键

  • 输入数据次序越乱,所选划分元素值的随机性越好,排序速度越快,快速排序不是自然排序方法。

  • 改变划分元素的选取方法,至多只能改变算法平均情况的下的时间性能,无法改变最坏情况下的时间性能。即最坏情况下,快速排序的时间复杂性总是O(n2)

选择排序

简单选择排序

基本思想:在待排序的数据中选出最大(小)的元素放在其最终的位置。

基本操作
  • 首先通过一次关键字比较,从 n 个记录中找出关键字最小的记录,将它与第一个记录交换
  • 再通过 n-2 次比较,从剩余的一个记录中找出关键字次小的记录,将它与第二个记录交换
  • 重复上述操作,共进行 n-1 趟排序后,排序结束

在这里插入图片描述

算法
void SeletSort(SqList &L) {for (i=1; i<L.length; ++i) { //n个元素需执行n-1趟k=i; RedType x; //临时变量用于位置交换for (j=i+1; j<=L.length; j++) { //每趟比较n-i次if (L.r[j].key < L.r[k].key) { //当发现较小值时记录其位置k=j;}}if (k!=i) { //将找到的位置和第i个元素位置交换x=L.r[i];L.r[i]=L.r[k];L.r[k]=x;}}
}
时间复杂度

记录移动次数:

  • 最好情况: 0

  • 最坏情况: 3(n-1)

比较次数,无论待排序列处于什么状态,选择排序所需进行的"比较"次数都相同 n(n-1)/2 (比较次数为n-1+n-2+…+1)

简单选择排序是不稳定排序

在这里插入图片描述

空间复杂度:需要一个辅助空间O(1)

堆排序
堆的定义

在这里插入图片描述

从堆的定义可以看出,堆实质是满足如下性质的完全二叉树

  • 二叉树中任一非叶子结点均小于(大于)它的孩子结点

在这里插入图片描述

堆排序定义

若在输出堆顶的最小值(最大值)后,使得剩余 n - 1 个元素的序列重又建成一个堆,则得到 n 个元素的次小值(次大值)“如此反复,便能得到一个有序序列,这个过程称之为堆排序。

如何在输出堆顶元素后,调整剩余元素为一个新的堆?

小根堆

​ a. 堆顶元素之同以堆中最后一个元素替代之,

​ b. 然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换

​ c. 重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为"筛选"
在这里插入图片描述

算法:

void HeapAdjust(elem R[], int s, int m) {/*已知R[s...m]中记录的关键字除了R[s]之外均满足堆的定义,本函数调整R[s]关键字,是R[s...m]成为一个大根堆*/rc=R[s]; //将根结点值放在rc中for (j=2*s; j<=m; j*=2) { //循环开始沿着较大的孩子节点向下筛选if (j<m && (R[j]<R[j+1])) ++j; //哪个孩子大就选哪个结点,左孩子大就取j,右孩子大就取j+1if (rc >= R[j]) break; // 当根节点大于孩子结点直接结束for循环(因为其他元素已经满足大根堆定义了)R[s]=R[j]; //将该大孩子结点值和此时根节点值互换,重新置for循环的j值为下面子树上的孩子结点位置,循环继续直到比较完s=j;}R[s]=rc; //最后将rc(原根节点)放到最终筛选出来的位置s上
}

堆的调整:对一个无序序列反复筛选就可以得到一个堆,即:从一个无序序列建堆的过程就是一个反复"筛选"的过程。

如何由一个无序序列建成一个堆?

  • 单结点的二叉树是堆;

  • 在完全二叉树中所有以叶子结点(序号 i > n/2 )为根的子树是堆。

  • 这样,我们只需依次将以序号为,n/2, n/2-1, …,1 的结点为根的子树调整为堆即可。即:对应由 n 个元素组成的无序序列,"筛选"只需从第n/2 个元素开始。

建立思想

  • 由于堆实质上是一个线形表,那么我们可以顶序存储一个堆

  • 创建一个小根堆的例:有关键字为 49 , 38 , 65 , 97 , 76 , 1 3 , 27 , 49 的一组记录,将其按关键字调整为一个小根堆。

    在这里插入图片描述

将初始无序的 R[1]到 R[n]建成小根堆可用以下语句实现,

for (i=n/2; i<=1; i--) {HeapAdjust(R, i, n);
}

堆排序

堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。

void HeapSort (elem R[]) { //对R[1]到R[n-1]进行堆排序int i;for (i=n/2; i>=1; i--) {HeapAdjust(R, i, n);  //创建初始堆}for (i=n; i>1; i--) {  //进行n-1趟排序Swap(R[1], R[i]);  //根与最后一个元素交换(相当于依次把元素有序从后往前放)HeapAdjust(R, i, i-1);  //对R[1]到R[i-1]重新建堆 }
}

算法性能分析:

  • 初始堆化所需时间不超过 O(n)

  • 排序阶段(不含初始堆化)

    • 一次重新堆化所需时间不超过 O(log n)
    • n-1 次循环所需时间不超过 O(n*log n)
    • Tw(n)=O(n)+ O(nlogn)= O(nlogn)
  • 堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下,其时间复杂度也为 O(nlogn), 这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列,都不会使堆排序处于"最好"或"最坏"的状态。

  • 另外,堆排序仅需一个记录大小供交换用的辅助存储空间。

  • 然而堆排序是一种不稳定的排序方法,它不适用于待排序记录个数 n较少的情况,但对于 n 较大的文件还是很有效的。

归并排序

基本思想

将两个或两个以上的有序子序列"归并"为一个有序序列,内部排序中通常采用2-路归并排序(每次归并2个元素)

即:将两个位置相邻的有序子序列 R[l…m]和 R[m+1…n]归并为一个有序序列 R[l…n]

在这里插入图片描述

整个归并排序仅需 ⌈ l o g 2 n ⌉ \lceil log~2~n \rceil log 2 n趟(向上取整加一)

关键问题:如何将两个有序序列合成一个有序序列?
在这里插入图片描述

算法

R[low] - R[mid]R[mid+1] - R[high] 为相邻,归并成一个有序序列R1[low] - R1[high]

SR[i].key <= SR[j].key, 则 TR[k] = RS[i]; k++; i++;否则, TR[k]=SR[j];k++; j++;

在这里插入图片描述

效率

时间效率:O(nlog2n)

空间效率: O(n) 因为需要一个与原始序列同样大小的辅助序列 (R1) 。这正是此算法的缺点。

稳定性:稳定

基数排序

基本思想

分配+收集

也叫桶排序或箱排序:设置若干个箱子,将关键字为 k 的记录放入第 k 个箱子,然后在按序号将非空的连接。

排序方法

数字是有范围的,均由 0 - 9这十个数字组成,则只需设置十个箱子,相继按个、十、百….进行排序.
在这里插入图片描述

性能分析

时间效率O(k*(n+m)) (n为扔出去元素个数,m为收回桶的个数,每一趟需要做n+m次(一扔一收),k个关键字,所以总共需要k*(n+m))

  • k: 关键字个数
  • m: 关键字取值范围为 m 个值

在这里插入图片描述

空间效率O(n+m)

稳定性:稳定

缺点:关键字的范围必须是一定的

各种排序方法比较

时间性能
  1. 按平均的时间性能来分,有三类排序方法:

    • 时间复杂度为 O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好;
    • 时间复杂度为 O(n2)的有: 直接插入排序、冒泡排序和简单选择排序,其中以直接插入为最好,特别是对那些对关键字近似有序的记录序列尤为如此;
    • 时间复杂度为 O(n) 的排序方法只有:基数排序。
  2. 当待排记录序列按关键顺序有序时,直接插入排序和冒泡排序能达到O(n)时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能退化为 O(n2),因此是应该尽量避免的情况。

  3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

空间性能

指的是排序过程中所需的辅助空间大小

  1. 所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为 O(1)
  2. 快速排序为 O(logn), 为栈所需的辅助空间
  3. 归并排序所需辅助空间最多,其空间复杂度为 O(n)
  4. 链式基数排序需附设队列首尾指针,则空间复杂度为 O(rd)
排序方法的稳定性能
  • 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。
  • 当对多关键字的记录序列进行 LS D 方法排序时,必须采用稳定的排序方法。
  • 对于不稳定的排序方法,只要能举出一个实例说明即可。
  • 快速排序和堆排序是不稳定的排序方法。
关于"排序方法的时间复杂度的下限"
  • 本章讨论的各种排序方法,除基数排序外,其它方法都是基于"比较关键字"进行排序的排序方法,可以证明,这类排序法可能达到的最快的时间复杂度为 O(nlogn)。(基数排序不是基于"比较关键字"的排序方法,所以它不受这个限制)。
  • 可以用一棵判定树来描述这类基于"比较关键字"进行排序的排序方法。

这是条美丽的分割线


To Be Continued for Next Series, 共勉~

这篇关于数据结构与算法基础(青岛大学-王卓)(9)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/288839

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int