做网站需要那些东西,网站搭建官网,俄语 俄文 俄罗斯语外贸网站建设,建好网站后最怎么维护算法设计
迭代法#xff1a;用于求方程的近似根。
1、若方程无解#xff0c;则算法求出的近似根序列就不会收敛#xff0c;迭代过程会变成死循环#xff0c;因此在使用迭代算法前应先考查方程是否有解#xff0c;并在程序中对迭代的次数给予限制。
2、方程虽有解#…算法设计
迭代法用于求方程的近似根。
1、若方程无解则算法求出的近似根序列就不会收敛迭代过程会变成死循环因此在使用迭代算法前应先考查方程是否有解并在程序中对迭代的次数给予限制。
2、方程虽有解但迭代公式选择不当或迭代的初始近似根选择不合理也会导致迭代失败。
穷举搜索法对可能是解的众多候选解按某种顺序进行逐一枚举和检查并从中找出符合要求的候选解作为问题的解
递推法利用问题本身所具有的一种递推关系求问题解的一种方法
递归法执行过程分递推和回归两个阶段在递推阶段把较复杂的问题的求解分解成比原问题简单一些的问题的求解。在回归阶段从获得的最简单情况的解逐级返回依次获得稍复杂问题的解。递归法就是把问题转化为规模缩小了的同类问题的子问题
分治法把大问题分解成一些较小的问题然后由小问题的解方便地构造出大问题的解每个小问题都是相互独立的。例如二分查找法、汉诺塔问题、斐波那契、归并排序
动态规划法基本思想也是将大问题分解为多个小问题但是与分治法不同的是动态规划法的子问题往往不是独立的。因此动态规划法可以避免大量重复的计算。以自底向上的方式计算出最优值。例如最大子段问题
贪心法不追求最优解只希望得到较为满意解的方法。可以快速得到满意的解不考虑整体情况所以贪心法不要回溯。例如哈夫曼编码
回溯法该方法首先暂时放弃关于问题规模大小的限制并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时就选择下一个候选解倘若当前候选键除了不满足问题规模要求外满足所有其他要求继续扩大当前候选解的规模并继续试探。如果当前候选解满足包括问题规模在内的所有要求该候选键就是问题的一个解。在回溯法中放弃当前候选解寻找下一个候选解的过程被称为回溯扩大当前候选解的规模以继续试探的过程称为向前试探回溯法以深度优先的方式搜索解空间树。
分支限界法类似于回溯法也是在问题的解空间树上搜索问题解的方法。但在一般情况下二者的求解目标不同。回溯法是找出解空间树中满足空间树中满足约束条件的解中找出使某一目标函数值达到极大或极小的解即在某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索空间树。例如单源最短路径问题
算法复杂度
例题
已知算法 A 的运行时间函数为 T(n)8T()其中 n 表示问题的规模则该算法的时间复杂度为1另已知算法 B 的运行时间函数为 T(n)XT()其中 n 表示问题的规模。对充分大的 n若要算法 B 比算法 A 快则 X 的最大值为2。 (1) A. O(n) B.O(nlogn) C.O() D.O()
(2) A. 15 B. 17 C. 63 D.65
一般地当递归方程为 T(n) aT(n/c) O(n)T(n)的解为
1. O(n)ac c 12. O(n)ac c 13. O(n)ac c 1
概率算法
数值概率算法适用于数值问题的求解这类算法得到的往往是近似解且近似解的精度随时间的增加不断提高。在多数情况下要计算出问题的精确解是不可能的或是没有必要的因此数值概率算法可得到相当令人满意的解。
蒙特卡罗算法适用于求问题的精确解该算法能求得一个解但该解未必是正确的正确的概率依赖算法所用的时间时间越久正确率越高。因此该算法的缺点就是无法有效地判断所得到的解是否正确。
拉斯维加斯算法如果该算法找到一个解那一定是正确的解得到正确解的概率依赖算法所用的时间。
舍伍德算法一定能找到一个正确的解该算法设法消除最坏情形与特定实例之间的关联性。
存储结构
顺序存储
适用于频繁用一组地址连续的存储单元依次存储线性表的各个数据元素查询时使用。 链式存储
在计算机中用一组任意的存储单元存储线性表的数据元素适用于在较频繁的插入、删除、更新元素时使用。
单链表 循环链表 双链表 因为双链表有两个指针域因此双链表的灵活度优于单链表但是双链表的开销要大一些。 顺序表与链表的比较
散列存储
将数据元素的存储位置与关键码之间建立确定对应关系的查找技术即键值对。 索引存储
索引是一个单独的、物理的数据库结构它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单比如数据库。 树
二叉树 性质 深度为K的二叉树最多有(2^K)-1个节点K1。 二叉树的第N层上最多有2^(N-1)个节点N1。 二叉树的叶子节点数等于度为2的节点数加1即n0n21。n0表示叶子节点数n2表示度为2的节点数。 满二叉树
如果一棵二叉树的节点要么是叶子节点要么它有两个子结点的树称满二叉树。
一棵深度为k且有(2^k)-1个节点的二叉树称为满二叉树。
除最后一层无任何子节点外每一层都上的所有节点都有两个子节点或0个子结点的二叉树 性质 层数为K的满二叉树的节点总数为(2^K)-1。 层数为K的满二叉树的叶子节点数为2^(K-1)。 完全二叉树
对一颗具有K个节点的二叉树按层序编号如果编号为i(1iK)的节点与满二叉树中编号为i的节点在二叉树中的位置完全相同那么这查二叉树称为完全二叉树。 性质 叶子节点只能出现在最下两层最下层的叶子节点集中在树的左边倒数第二层的叶子节点一定出现在右边。 节点度为1则该节点只有左子树即不存在只有右子树的情况。 具有N个节点的完全二叉树的深度为⌊logN⌋1logN表示以2为底N的对数⌊X⌋表示不大于X的最大整数。 如果对一棵有N个节点的完全二叉树的节点按层序编号则对任一节点index(1indexN)满足以下条件 若index1节点index是二叉树的根无双亲若index1则[i / 2]是双亲节点。 若2*indexN节点index无左孩子否则2*index为左孩子节点。 若2*index1N节点index无右孩子否则2*index1为右孩子节点。 注满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。 四种遍历方式
前序遍历
遍历顺序根 左 右 中序遍历
遍历顺序 左 根 右 后序遍历
遍历顺序左 右 根 层序遍历
遍历顺序逐层遍历 哈夫曼树最优二叉树
定义哈夫曼树是带权路径WPL最短的树权值越大的叶子节点越靠近根节点。
WPL值的计算树的路径长度是从树根到每一结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和通常记作WPL。
以数组 【5,29,7,8,14,23,3,11】为例下面是计算哈夫曼树 WPL 的详细过程。 排序按照数组中元素的权值进行升序排序。 排序后的数组【3,5,7,8,11,14,23,29】 构建哈夫曼树 依次从数组中取出两个权值最小的元素构建一个新的节点其权值为这两个元素的权值之和。将这个新节点放回数组并继续排序直到数组中只剩一个节点即哈夫曼树的根节点。 第一步【3,5,7,8,11,14,23,29】 构建新节点35得到【8,7,8,11,14,23,29】第二步7,8,8,11,14,23,29 构建新节点78得到【15,8,11,14,23,29】第三步【8,11,14,15,23,29】 构建新节点811得到【19,14,15,23,29】第四步【14,15,19,23,29】 构建新节点1415得到【29,19,23,29】第五步【19,23,29,29】 构建新节点1923得到【42,29,29】第六步【29,29,42】 构建新节点2929得到【58,42】第七步【42,58】 构建新节点4258得到【100】 计算 WPL 计算哈夫曼树的 WPL 值。对于每个叶子节点其带权路径长度等于该节点的权值乘以到达该节点的路径长度。最后将所有叶子节点的带权路径长度相加即可。 WPL(4578)*4(1114)*3(2329)*2 967552 275
例题
已知一个文件中出现的各字符及其对应的频率如下表所示。若采用定长编码则该文件中字符的码长应为1。若采用Huffman编码则字符序列“face”的编码应为2。
字符abcdef频率%4513121695
(1) A2 B3 C4 D5
(2) A110001001101 B001110110011 C101000010100 D010111101011
解析所谓定长编码是指用多少位二进制足够表示字符图中字符是有6个的a、b、c、d、e、f可用000到101表示a到f这样编码字符的码长可以为34位当然也是可以但我们是找最合适的自然3位能满足要求。第二问哈夫曼树的左节点未必要比右节点小但是通常做题时需要写成左小右大的形式再左0右1赋值所谓“face”编码是指找到这4个字母从根节点出发要经历的编码数。如下图所示所以答案为B A 二叉排序树 性质 若任意结点的左子树不空则左子树上所有节点的值均不大于它的根节点的值。 若任意结点的右子树不空则右子树上所有节点的值均不小于它的根节点的值。 任意节点的左、右子树也分别为二叉搜索树 平衡二叉树
具备以下性质的二叉搜索树称为平衡二叉树。 性质 每个节点的的左子树和右子树的高度之差的绝对值不超过1。 平衡因子 左子树的深度 - 右子树的深度 森林
树转二叉树
转换原理 加线将所有兄弟节点连成一条线。 去线对树中每个节点只保留它与每一个孩子节点的连线删除其它孩子节点的连线。 二叉树转树
转换原理 加线如果根节点的左节点存在则将根节点的所有右节点与根节点连成一条线。 去线删除原二叉树中所有节点与右节点的连线。 层次调整。
森林转二叉树
转换原理 将森林中的每一棵树转换成二叉树。 连线将每棵树的根节点连成一条线。 二叉树转森林
转换原理 只要存在右孩子节点就不断删除右孩子节点的连线。 将分离后的二叉树转换成树。
图
邻接矩阵
无向图其邻接矩阵第i行的元素的和即为顶点 i 的度
例如顶点4的度就是第四行的和即2。 有向图其邻接矩阵第i行元素之和为顶点i的出度而邻接矩阵的第j列元素之和为顶点j的入度。
查找算法
二分查找法
适用情况
不经常变动而查找频繁的有序列表
优点
1、比较次数少
2、查找速度快
3、平均性能好
缺点
1、要求待查表为有序表
2、插入删除困难
实现算法首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。
分块查找法
适用情况节点动态变化的情况
优点比顺序查找算法快得多
缺点速度不如折半查找法
实现算法把一个线性表分成若干个块每块中的节点可以任意存放但块与块之间必须排序。假设是按关键码值非递减的那么这种块与块之间必须满足已排序要求实际上就是对于任意的i第i 块中的所有节点的关键码值都必须小于第i1块中的所有节点的关键码值。此外还要建立一个索引表把每块中的最关键码值作为索引表的关键码值按块的顺序存放到一个辅助数组中显然这个辅助数组是按关键码值递减排序的。查找时首先在索引表中进行查找确定要找的节点所在的块。由于索引表的排序的因此对索引表的查找可以采用顺序查找或折半查找;然后在相应的块中采用顺序查找即可找到对应的节点
平均查找长度
1以二分查找确定块时平均查找长度 log2(n / s1) s / 2
2以顺序查找确定块时平均查找长度 (b 1) / 2 (s 1) / 2 (s^2 2s n) / 2s
注n 表示元素的总个数
s 表示每个块所具有的元素个数
b 表示分为几个块
排序算法 例题
堆是一种数据结构(34) 是堆排序
A(1050803060201518)
B(1018152050803060)
C(1015185080306020)
D(1030602015185080)
归并排序的归并路数
归并路数 | |其中m为元素个数k为多路归并趟数。
例题若对 27 个元素只进行 3 趟多路归并排序则选取的归并路数为37
A. 2 B. 3 C. 4 D. 5
广义表
广义表的长度是将最外面那层的括号删了以后所剩下的元素组个数深度是括号的层数。
例题L1((a,(a,b),((a,b),c))), L2((1,2,3)), L3(1,2,3)。求L1、L2、L3的长度和深度
长度深度L114L212L331
未完待续......
