【整理】算法说明书

您所在的位置：网站首页 › 系统配置与程序运行说明书怎么写 › 【整理】算法说明书

【整理】算法说明书

2024-07-16 19:46| 来源: 网络整理| 查看: 265

Hailstone序列

在这里插入图片描述

程序 ≠ 算法对于任意的n，总有 | Hailstone(n) | < 无穷？ Turing Machine图灵机

在这里插入图片描述

构成部件： Tape带：依次均匀地划分为单元格，各存有某一字符，初始均为 ‘#’Alphabet字符表：字符的种类有限Head读写头：总是对准某一单元格，并可读取或改写其中字符；每经过一个节拍，可转向左或右侧邻格State状态：有限状态的一种，每经过一个节拍，可按照规则转向另一种状态转换函数： Transition Function: (q, c; d, L/R, p)若当前状态为q，且当前字符为c，则将当前字符改为d，转向左/右侧邻格，并转入‘p’状态当状态为 ‘ h ’ = halt，则停机 RAM（Random Access Machine）

在这里插入图片描述

寄存器顺序编号，总数没有限制每一基本操作仅需常熟时间可通过编号直接访问任意寄存器（call-by-rank）将算法的运行时间转换为算法需要执行的基本操作次数 2-Subset：NPC

在这里插入图片描述

定理：| 2S| = 2^| S |^ = 2n2-Subset is NP-complete，就目前的计算模型而言，不存在可在多项式时间内回答此问题的算法。封底估算（Back-Of-Envelope Calculation）

在这里插入图片描述

减而治之Decrease-and-conquer

为求解一个大规模问题，可以将其分解为：其一平凡，另一规模缩减的两个子问题。在这里插入图片描述

分而治之Divide-and-conquer

为求解一个大规模问题，可以将其分解为若干个（通常为两个）子问题，规模大体相当。在这里插入图片描述

大师定理/主定理/Master Theorem 在这里插入图片描述

fibonacci数递归版fibonacci数低效根源：各递归实例均被大量重复地调用在这里插入图片描述

迭代 · memoization（制表备查） · 颠倒计算方法：自底向上递归在这里插入图片描述

LCS(Longest Common Sbusequence)最长公共子序列方法1（递归）：最好O(n+m); 最差O(2n) 递归基：若n=-1或m=-1，则取做空序列减而治之：若A[n] = ‘X’ = B[m]，则LCS(n-1, m-1)+‘X’分而治之：A[n] ≠ B[m]，则LCS(n, m-1)与LCS(n-1, m)中取更长者在这里插入图片描述

方法2（动态规划—迭代）：O(n*m) 在这里插入图片描述

单调性：每经过一次比对，至少一个序列的长度缩短一个单位可扩容向量容量加倍策略在这里插入图片描述

容量递增策略 T*oldElem = _elem; _elem = New T[_capacity += INCREMENT]对比在这里插入图片描述

有序向量唯一化低效版O(n2)：在有序向量中，重复的元素必然相互紧邻构成一个区间，每一个区间只需保留单个元素即可。低效根源：同一元素可作为被删除元素的后继多次前移高效版O(n)：将同一元素作为一个区间，不同元素覆盖在其第一个元素后有序向量查找 1. 二分查找A 复杂度：线性递归 T(n) = T(n/2) + O(1) = O(nlogn)递归跟踪：轴点总能取到中点，递归深度O(nlogn)，各递归实例仅耗时O(1)成功、失败时的平均查找长度均为O(1.5logn)以任一元素S[mi] 为界都可将待查找区间 [lo,hi) 分为三部分，且 S[lo,hi)

【本文地址】

【整理】算法说明书

【整理】算法说明书

今日新闻

推荐新闻