Java教程

大学算法期末笔记

本文主要是介绍大学算法期末笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

PPT1

考点:image-20210701111027782

image-20210630220649823

概念:

image-20210701105009706

image-20210701105034679

image-20210701110224167

image-20210701110925767

image-20210701120345241

image-20210701111319703

image-20210701114528774

image-20210701114654792

image-20210701114343305

伪代码:

image-20210701110444295

  • 就像华容道,始终空一格,由于Key已经拿了出来,不用担心右边被左边覆盖,所以比它大就往右挪,直到不大于Key,就把Key填到格子里。
  • 这里是>,但有的是>=(不是≥)

image-20210701120224279

image-20210701114332489image-20210701120139388

image-20210701120827432

帮助理解:

image-20210701120537080

image-20210701110726775

PPT2

考点:

image-20210630220710383

image-20210701111027782

概念:

image-20210701121158600

image-20210701121448587

image-20210701122138666

image-20210701121556472

image-20210701124033164

image-20210701131404333

image-20210701131622075

image-20210701131637964

伪代码:

image-20210701122313353

  • if p < r,很多算法都有这个前提

image-20210701123550281

image-20210701125854121

image-20210701125811321

image-20210701123715433

image-20210701124145388

  • 没有写函数体,直接写了函数名字,最后还要加上一个return。

  • for j=p to r-1 exchange…with…

  • for…to return 等等,没有括号

image-20210701125738429

image-20210701130445259

image-20210701130456396

  • 注意是lgn不是logn

image-20210701130541086

image-20210701131118719

  • 除了用一个A[随机数]交换了A[r]再分解,其他的地方都一样

image-20210701131508636

image-20210701131712299

image-20210701135224436

  • i与它的左右子树相比较,在三者不大于heapsize的基本前提下,如果A[i]不是最大的那个,就和A[largest]互换。注意lc,rc,i,largest都是序号。image-20210701135119908

image-20210701132449709

  • 上图是维护最大堆的T(n)。image-20210701134102693

帮助理解:

image-20210701125159981

  • r的位置不能预先确定,i来划分两个分区,j来遍历每个数,如果A[j]比4小,就把i右边的大数和a[j]互换,相当于变相增加了小数区间,大数区间整体右移。直到j=r-1.然后把r和i右边(i+1)换个位置,插入进去就好了。

image-20210701134617989

  • 先乱序堆,然后堆排序。大根堆和最小值交换,最大值回到数组,堆排序再次得到大根堆,此时大根堆是第二大值,再交换,以此类推。

递归式求解——代入法、递归树与主定理 - 知乎 (zhihu.com)

1.6 快速排序 | 菜鸟教程 (runoob.com)

(12条消息) 什么是二叉堆?_stay hungry ! stay foolish!-CSDN博客_二叉堆

[图解] 快速排序 - 简书 (jianshu.com)

PPT3

考点:image-20210630220719711

概念:image-20210701134247763

image-20210701134859317

image-20210701135334019

image-20210701135351651

image-20210701135411779

image-20210701140457380

伪代码

image-20210701135431571

  • length(s) si>=fj A U {i} j <- i

image-20210701135637092

image-20210701140216532

image-20210701140230612

  • 此时已经有了具体的乱序

image-20210701140259365

image-20210701140321269

image-20210701140345989

  • 别忘了rank[x]++ rank是深度

image-20210701140426980

  • G是图,W是权重,U和V是边

image-20210701140440500

理解记忆:

image-20210701135743381

image-20210701135836739

image-20210701140015604

image-20210701140105039

image-20210701140045571

image-20210701140129075

  • 查询是int,其他是union

贪心算法:贪心选择性与优化子结构 (itxueyuan.com)

(6条消息) 哈夫曼编码(最优前缀码)_Debuging-CSDN博客

(6条消息) 算法导论–最小生成树(Kruskal和Prim算法)_勿在浮砂筑高台-CSDN博客_prim算法

傻子都能看懂的并查集入门 - SegmentFault 思否

(6条消息) 分治法,动态规划及贪心算法区别_longwufengfei的专栏-CSDN博客

PPT4

考点:

image-20210630220740816

概念:

image-20210701140544742

image-20210701140721668

image-20210701140744726

image-20210701140756276

image-20210701141051587

image-20210701140844774

image-20210701141118917

伪代码

image-20210701140823222

image-20210701141158213

image-20210701141221958

image-20210701141231557

image-20210701141322149

image-20210701141428775

image-20210701141440629

image-20210701141449828

image-20210701141500581

image-20210701141508038

帮助理解:

image-20210701140912420

image-20210701140943320

(6条消息) 分治法,动态规划及贪心算法区别_longwufengfei的专栏-CSDN博客

(6条消息) 动态规划 最长公共子序列 过程图解_hrn1216的博客-CSDN博客_最长公共子序列

算法设计与分析——矩阵连乘问题(动态规划) - 王陸 - 博客园 (cnblogs.com)

这篇关于大学算法期末笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!