主要算法

⑴ 操作系统的主要算法都有哪些

一、进程(作业)调度算法
l 先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。

l 短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。

l 时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。

l 优先数调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。

l 响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。

l 多级队列调度算法

基本概念：

作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

作业平均周转时间(T)＝周转时间/作业个数

作业带权周转时间（Wi）＝周转时间/运行时间

响应比＝（等待时间＋运行时间）/运行时间

二、存储器连续分配方式中分区分配算法
n 首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。

n 循环首次适应算法：每次分配均从上次分配的位置之后开始查找。

n 最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。

三、页面置换算法
l 最佳置换算法（OPT) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

l 先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。

l 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

l 最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

四、磁盘调度
n 先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

n 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

n 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

n 循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。

⑵ D*算法的主要方法

1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。
原OPEN和CLOSE中节点信息保存。
2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y->X->G），Y是当前点。k值取h值变化前后的最小。

⑶ 机器学习的主要算法。

机器学习算法很多。经典的有：
决策树、贝叶斯学习、神经网络、遗传算法。
想深入学习建议看看米歇尔的机器学习。

⑷ 算法的主要特征

算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。对于该类问题的任何初始输入值，它都能机械地一步一步地执行计算，经过有限步骤后终止计算并产生输出结果。归纳起来，算法具有以下基本特征：
(1) 有穷性：一个算法必须在执行有限个操作步骤后终止；
(2) 确定性：算法中每一步的含义必须是确切的，不可出现任何二义性；
(3) 有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数被0除的操作就是无效的，应当避免这种操作。
(4) 有零个或多个输入：这里的输入是指在算法开始之前所需要的初始数据。这些输入的多少取决于特定的问题。例如，例l-1的算法中有2个输入，即需要输入a和b两个初始数据，而例l-2的算法中则需要输入四个初始数据。有些特殊算法也可以没有输入。
(5) 有一个或多个输出：所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。如上述关于算法的三个例子中，每个都有输出。试想，如果例1-3中没有 "输出n的当前值"这一步，这个算法将毫无意义。

⑸ 算法分析的两个主要方面是

空间复杂性和时间复杂性。

时间复杂度和空间复杂度是衡量算法好差的重要指标，正确性和简洁性、可读性和可运行性是从软件工程角度要求系统实现的目标。

一个算法应包含有限的操作步骤，而不能是无限的，事实上有穷性往往是在合理的范围之内，如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，不能将其视为有效算法。

(5)主要算法扩展阅读：

算法分析注意事项：

循环结构是算法教学的重点和难点，要注意分散此难点，做到循序渐进，逐层深入，例如在教算法含义时先渗透一点循环结构的知识，在教算法3 种基本结构时可先给出循环结构的一些简单的例子，到了教条件语句和循环语句时再逐步加深。

输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。算法分析是计算复杂度理论的重要组成部分。

⑹ 平衡树的主要算法

红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。
红黑树有两个特征：
(1) 节点都有颜色
(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
红黑规则：
1. 每一个节点不是红色的就是黑色的
2. 根总是黑色的
3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）
4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。
（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置） AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：
(1) 其根的左右子树高度之差的绝对值不能超过1；
(2) 其根的左右子树都是二叉平衡树。
AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。
AVL树插入的C++代码： template<classT>ResultCodeAVLTree<T>::Insert(AVLNode<T>*&p,T&x,bool&unBalanced)...{ResultCoderesult=Success;if(p==null)...{//插入新节点p=newAVLNode<T>(x);unBalanced=true;}elseif(x<p->element)...{//新节点插入左子树result=Insert(p->lChild,x,unBalanced);if(unBanlanced)...{switch(p->bF)...{case-1:p->bF=0;unBalanced=false;break;case0:p->bF=1;break;case1:LRotation(p,unBalanced);}}}elseif(x==p->element)...{//有重复元素，插入失败unBalanced=false;x=p->element;result=Duplicate;}else...{//新节点插入右子树result=Insert(p->rChild,x,unBalanced);if(unBalanced)...{switch(p->bF)...{case1:p->bF=0;unBalanced=false;break;case0:p->bF=-1;break;case-1:RRotation(p,unBalanced);}}}returnresult;}template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced)...{AVLNode<T>*u,*r=s->lChild;if(r->bF==1)...{//LL旋转s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子树的根}else...{//LR旋转u=r->rChild;r->rChild=u->lChild;u->lChild=r;s->lChild=u->rChild;u->rChild=s;switch(u->bF)...{case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break;case-1:s->bF=0;r->bF=1;}s=u;//s指示新子树的根}s->bF=0;//s的平衡因子为0unBalanced=false;//结束重新平衡操作}通常我们使用二叉树的原因是它可以用O（logn）的复杂度来查找一个数，删除一个数，对吧？？可是有时候会发现树会退化，这个就可能使O（logn）->O（n）的了，那么还不如用直接搜一次呢！！所以我们就要想办法使一棵树平衡。而我仅仅看了（AVL）的那个，所以也仅仅能说（AVL）的那个，至于（TREAP），我还不懂，如果你们知道算法的话，欢迎告诉我~！谢谢~
首先引入一个变量，叫做平衡因子（r），节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡，就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0，-1，1.
其次，我要介绍旋转，旋转有两种方式，就是左旋（顺时针旋转）和右旋（逆时针旋转）。
左旋（左儿子代替根）：即用左儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把L的右儿子取代X的左儿子，然后把更新后的X赋值为L的右儿子，就可以了。
右旋（右儿子代替根）：即用右儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把R的左儿子取代X的右儿子，然后把更新后的X赋值为R的左儿子，就可以了。 Size Balanced Tree(SBT平衡树）是2007年Winter Camp上由我国着名OI选手陈启峰发布的他自己创造的数据结构。相比于一般的平衡树，此平衡树具有的特点是：快速（远超Treap，超过AVL)、代码简洁、空间小（是线段树的1/4左右）、便于调试和修改等优势。
与一般平衡搜索树相比，该数据结构只靠维护一个Size来保持树的平衡，通过核心操作Maintain(修复）使得树的修改平摊时间为O(1)。因而大大简化代码实现复杂度、提高运算速度。
参见网络SBT。 平衡树的一种，每次将待操作节点提到根，每次操作时间复杂度为O(logn)。见伸展树。 constintSPLAYmaxn=200005;constintSPLAYinf=100000000;structSplay_Node{intl,r,fa,v,sum;};structSplay{Splay_Nodet[SPLAYmaxn];introot,tot;voidcreate(){root=1,tot=2;t[1].v=-SPLAYinf;t[2].v=SPLAYinf;t[1].r=t[1].sum=2;t[2].fa=t[2].sum=1;}voipdate(intnow){t[now].sum=t[t[now].l].sum+t[t[now].r].sum+1;}voidleft(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].r=t[now].l;t[t[now].l].fa=fa;t[now].l=fa;up(fa);}voidright(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].l=t[now].r;t[t[now].r].fa=fa;t[now].r=fa;update(fa);}voidsplay(intnow,intFA=0){while(t[now].fa!=FA){intfa=t[now].fa;if(t[fa].fa==FA)if(t[fa].l==now)right(now);elseleft(now);elseif(t[t[fa].fa].l==fa)if(t[fa].l==now)right(fa),right(now);elseleft(now),right(now);elseif(t[fa].l==now)right(now),left(now);elseleft(fa),left(now);}update(now);if(!FA)root=now;}intlower_bound(intv){intans=0,la=0;for(intnow=root;now;){la=now;if(t[now].v>=v)ans=now,now=t[now].l;elsenow=t[now].r;}splay(la);returnans;}voidinsert(intv){for(intnow=root;;){++t[now].sum;if(t[now].v>=v)if(t[now].l)now=t[now].l;else{t[now].l=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}elseif(t[now].r)now=t[now].r;else{t[now].r=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}}}intget_lower(inta){splay(a);for(a=t[a].l;t[a].r;a=t[a].r);returna;}intget_upper(inta){splay(a);for(a=t[a].r;t[a].l;a=t[a].l);returna;}intget_rank(inta){splay(a);returnt[t[a].l].sum;}voiddel(intl,intr){l=get_lower(l);r=get_upper(r);splay(l);splay(r,l);t[r].l=0;update(r);update(l);}intget_kth(intk){++k;for(intnow=root;;){if(t[t[now].l].sum==k-1)returnnow;if(t[t[now].l].sum>=k)now=t[now].l;elsek-=t[t[now].l].sum+1,now=t[now].r;}}};

⑺ 常见的深度学习算法主要有哪些

深度学习常见的3种算法有：卷积神经网络、循环神经网络、生成对抗网络。
卷积神经网络(Convolutional Neural Networks, CNN)是一类包含卷积计算且具有深度结构的前馈神经网络(Feedforward Neural Networks)，是深度学习的代表算法之一。
循环神经网络(Recurrent Neural Network, RNN)是一类以序列数据为输入，在序列的演进方向进行递归且所有节点(循环单元)按链式连接的递归神经网络。
生成对抗网络(GAN, Generative Adversarial Networks )是一种深度学习模型，是最近两年十分热门的一种无监督学习算法。

⑻ 一个算法的评价主要从哪些方面来考虑

一个算法的评价主要从以下几个方面来考虑：

1、时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

T(n)=Ο(f(n))

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

2、空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

3、正确性

算法的正确性是评价一个算法优劣的最重要的标准。

4、可读性

算法的可读性是指一个算法可供人们阅读的容易程度。

5、健壮性

健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

(8)主要算法扩展阅读：

算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。

算法可以宏泛的分为三类：

一、有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二、有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。

三、无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。

⑼ 统计模型和大数据模型所使用的主要算法有什么异同

以每24小时作为一份时间（而非自然日），根据用户的配置有两种工作模式：带状模式中，用户仅定义开始日期时，从开始日期（含）开始，每份时间1个分片地无限增加下去；环状模式中，用户定义了开始日期和结束日期时，以结束日期（含）和开始日期（含）之间的时间份数作为分片总数（分片数量固定），以类似取模的方式路由到这些分片里。

1. DBLE 启动时，读取用户在 rule.xml 配置的 sBeginDate 来确定起始时间
2. 读取用户在 rule.xml 配置的 sPartionDay 来确定每个 MySQL 分片承载多少天内的数据
3. 读取用户在 rule.xml 配置的 dateFormat 来确定分片索引的日期格式
4. 在 DBLE 的运行过程中，用户访问使用这个算法的表时，WHERE 子句中的分片索引值（字符串），会被提取出来尝试转换成 java 内部的时间类型
5. 然后求分片索引值与起始时间的差，除以 MySQL 分片承载的天数，确定所属分片

1. DBLE 启动时，读取用户在 rule.xml 配置的起始时间 sBeginDate、终止时间 sEndDate 和每个 MySQL 分片承载多少天数据 sPartionDay
2. 根据用户设置，建立起以 sBeginDate 开始，每 sPartionDay 天一个分片，直到 sEndDate 为止的一个环，把分片串联串联起来
3. 读取用户在 rule.xml 配置的 defaultNode
4. 在 DBLE 的运行过程中，用户访问使用这个算法的表时，WHERE 子句中的分片索引值（字符串），会被提取出来尝试转换成 Java 内部的日期类型
5. 然后求分片索引值与起始日期的差：如果分片索引值不早于 sBeginDate（哪怕晚于 sEndDate），就以 MySQL 分片承载的天数为模数，对分片索引值求模得到所属分片；如果分片索引值早于 sBeginDate，就会被放到 defaultNode 分片上

与MyCat的类似分片算法对比

中间件
DBLE
MyCat

分片算法种类 date 分区算法 按日期（天）分片
两种中间件的取模范围分片算法使用上无差别

开发注意点
【分片索引】1. 必须是字符串，而且 java.text.SimpleDateFormat 能基于用户指定的 dateFormat 来转换成 java.util.Date
【分片索引】2. 提供带状模式和环状模式两种模式
【分片索引】3. 带状模式以 sBeginDate（含）起，以 86400000 毫秒（24 小时整）为一份，每 sPartionDay 份为一个分片，理论上分片数量可以无限增长，但是出现 sBeginDate 之前的数据而且没有设定 defaultNode 的话，会路由失败（如果有 defaultNode，则路由至 defaultNode）
【分片索引】4. 环状模式以 86400000 毫秒（24 小时整）为一份，每 sPartionDay 份为一个分片，以 sBeginDate（含）到 sEndDate（含）的时间长度除以单个分片长度得到恒定的分片数量，但是出现 sBeginDate 之前的数据而且没有设定 defaultNode 的话，会路由失败（如果有 defaultNode，则路由至 defaultNode）
【分片索引】5. 无论哪种模式，分片索引字段的格式化字符串 dateFormat 由用户指定
【分片索引】6. 无论哪种模式，划分不是以日历时间为准，无法对应自然月和自然年，且会受闰秒问题影响

运维注意点
【扩容】1. 带状模式中，随着 sBeginDate 之后的数据出现，分片数量的增加无需再平衡
【扩容】2. 带状模式没有自动增添分片的能力，需要运维手工提前增加分片；如果路由策略计算出的分片并不存在时，会导致失败
【扩容】3. 环状模式中，如果新旧 [sBeginDate,sEndDate] 之间有重叠，需要进行部分数据迁移；如果新旧 [sBeginDate,sEndDate] 之间没有重叠，需要数据再平衡

配置注意点
【配置项】1. 在 rule.xml 中，可配置项为 <propertyname="sBeginDate"> 、 <propertyname="sPartionDay"> 、 <propertyname="dateFormat"> 、 <propertyname="sEndDate"> 和 <propertyname="defaultNode">
【配置项】2.在 rule.xml 中配置 <propertyname="dateFormat">，符合 java.text.SimpleDateFormat 规范的字符串，用于告知 DBLE 如何解析sBeginDate和sEndDate

【配置项】3.在 rule.xml 中配置 <propertyname="sBeginDate">，必须是符合 dateFormat 的日期字符串

【配置项】4.在 rule.xml 中配置 <propertyname="sEndDate">，必须是符合 dateFormat 的日期字符串；配置了该项使用的是环状模式，若没有配置该项则使用的是带状模式

【配置项】5.在 rule.xml 中配置 <propertyname="sPartionDay">，非负整数，该分片策略以 86400000 毫秒（24 小时整）作为一份，而 sPartionDay 告诉 DBLE 把每多少份放在同一个分片

【配置项】6.在 rule.xml 中配置 <propertyname="defaultNode"> 标签，非必须配置项，不配置该项的话，用户的分片索引值没落在 mapFile 定义

⑽ 现在密码学采用的算法主要有什么

现代密码学将算法分为具有不同功能的几种
常用的主要有三种：
1.对称密码算法
DES算法——二十世纪七十年代提出，曾经称霸对称加密领域30年
AES算法——二十一世纪初提出用以取代DES算法
IDEA算法——二十世纪九十年代初提出，也是一种流行算法
RC4算法——经典的流密码算法
2.公钥密码算法
D-H算法——用于密钥协商，是第一种使用的公钥算法，基于离散对数难解问题
RSA算法——最常用的公钥算法，功能强大
3.哈希函数(杂凑函数)
MD5——常用算法，用于产生80比特的输出
SHA-1——也是常用算法，用于产生128比特输出
---
这是最经典的若干种算法
说的不对之处请指正

------
个人意见 仅供参考