学习]算法导论第一章导论

格式：pdf
大小：2.62 MB
文档页数：25

下载文档原格式

/ 25

算法导论笔记

第一章算法在计算中的应用第九章中位数和顺序统计学9.1-11.将数组中的元素分组，每组两个元素，然后比较每组中的两个元素得到最小值，重新得到包含原来一半元素的数组，继续重复上述过程，那么最后一个元素必然为最小值。

如图所示，数组为{2, 1, 4, 3, 5}2.上述过程形成的是一个二叉树，其中叶子节点都为数组元素，非叶子节点刚好4个，这是二叉树的性质。

3.然后我们来找第二小元素，第二小元素必然跟着1，首先赋值为5，然后再赋值为3，然后赋值为2，即为所求。

【运行结果】：1.我们先将N个数配对，每两个数一对，每对之间进行互相比较得出小值。

2.对得出的N/2个元素重复第一步，直至得出最小值。

到这儿我们得出了最小值，实际上比较的次数为n-1次。

不难发现上面的过程实际上可以演示为一个二叉树。

例如在5,8,11,18四个数找出最小值，二叉树演示如下（每个节点相当于一次比较）：观察二叉树，可以得出这样一个结论，所有与最小值比较过的数中的最小值纪即为第二小的的值。

二叉树的高度为lgn，因此与最小值比较的数的数目为lgn,在lgn个数中找出最小值要进行lgn-1次比较。

9.1-29.3节的方法可以在最坏情况下的线性复杂度的算法来求顺序统计量.其核心思想在于获得一个更好的中枢值来更好地划分数组.然而题中给了我们一个"黑盒子"来以线性复杂度获取一个真正好的中枢值，那么再好不过了。

在同时找到最大值和最小值时，每个元素都参与了与最大值和最小值的比较，比较了两次。

将数组成对处理。

两两互相比较，将大的与最大值比较，小的与最小值比较。

每两个元素需要的比较次数是，两两比较一次，大者与最大值比较一次，小者与最小值比较一次，共三次。

9.2-1长度为0的数组，RANDOMIZED-SELECT直接返回，当然不会递归调用。

9.2-29.2-3 写出RANDOMIZED-SELECT的一个迭代版本【算法思想】：递归：在函数中调用自身的程序过程。

算法导论第1次课

n
Βιβλιοθήκη n最好情况：输入数据状态为升序，此时A[i]≤key，所以tj=1 T(n) = C1n+C2(n-1)+C3(n-1)+C4(n-1)+C7(n-1) = (C1+C2+C3+C4+C7)n-(C2+C3+C4+C7) = An+B 最坏情况：输入数据状态为倒序，此时A[i]>key，所以tj=j T(n) = C1n+C2(n-1)+C3(n-1)+C4 = ½(C4+C5+C6)n2+(C1+C2+C3+½C4-½C5 -½C6+C7)n-(C2+C3+C4+C7) = An2+Bn+C
特别提示，大O既可表示紧上界也可表示松上界。
2.3 Ω符号(渐进下界) def: Ω(g(n)={f(n):存在正常数C和n0，使得对于所有的n≥n0，都有0≤Cg(n)≤f(n)} 记为：f(n) = Ω(g(n))
例5：证明f(n)=3n2 = Ω(n) proof: 即要证 Cn≤3n2 Θ,O,Ω符号之间存在关系如下：定理3.1（P29）对于任意的函数f(n)和g(n)，当且仅当f(n)=O(g(n))且 f(n)=Ω(g(n))时，f(n)=Θ(g(n))。
1 例6：f (n ) n(n 1), g(n ) n 2 2 例7：f (n ) l g n, g(n ) n
第二章渐进符号(Asympototic notation)
2.1 Θ符号(渐近符号)
def: Θ(g(n)) = { f(n):存在大于0的常数C1、C2和n0，使得

计算机算法基础(第一章)

·作为算法分析的数据集：典型特征 ·作为程序性能测试的数据集：对执行指标产生影响的性质
3. 如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο 、Ω）——与计算机物理软硬件没有直接关系。
目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。
分析手段：作时、空性能分布图
4. 计算时间的渐近表示
记：算法的计算时间为f(n) 数量级限界函数为g(n)
其中，
n是输入或输出规模的某种测度。 f(n)表示算法的“实际”执行时间—与机器及语言有关。 g(n)是形式简单的函数，如nm，logn，2n，n!等。是事
在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。
数量级
语句的数量级：语句的执行频率
例：1，n ，n2
算法的数量级：算法所包含的所有语句的执行频率之和。
算法的数量级从本质上反映了一个算法的执行特性。
例：假如求解同一个问题的三个算法分别具有n， n2 ， n3数量级。若n=10，则可能的执行时间将分别是10，100，1000个单位时间——与环境因素无关。
计算机算法基础
参考书目
算法导论（第二版影印版）Introduction to Algorithms(Second Edition )
（美）Thomas H.Cormen等高等教育出版社
计算机程序设计艺术（英文影印版）（1-3卷精装全套）The Art of Computer Programming Volumes 1-3 Boxed Set （美）Donald E.Knuth 清华大学出版社

算法导论复习资料

算法导论复习资料一、选择题：第一章的概念、术语。

二、考点分析：1、复杂度的渐进表示，复杂度分析。

2、正确性证明。

考点：1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，©，替换法证明，先猜想，然后给出递归方程）。

循环不变性的三个性质：1）初始化：它在循环的第一轮迭代开始之前，应该是正确的；2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。

插入排序算法：【INSERTION-SORT(A)1 for j ←2 to length[A]2 do key ←A[j]3 ▹Insert A[j] into the sorted sequence A[1，j - 1].4 i ←j - 15 while i > 0 and A[i] > key6 do A[i + 1] ←A[i]7 i ←i - 18 A[i + 1] ←key插入排序的正确性证明：课本11页。

》归并排序算法：课本17页及19页。

归并排序的正确性分析：课本20页。

3、分治法（基本步骤，复杂度分析）。

——许多问题都可以递归求解考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。

（解：共有24种状态，至少称重3次可以找出不同的球）不是考点：线性时间选择，最接近点对，斯特拉算法求解。

解：基本步骤：一、分解：将原问题分解成一系列的子问题；二、解决：递归地解各子问题。

若子问题足够小，则直接求解；三、合并：将子问题的结果合并成原问题的解。

复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式、T(n)=Q(1) n<=cT(n)=aT(n/b)+D(n)+C(n) n>c附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S 和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

[1]算法导论

实例：求最大公约数
算法1.1 Euclid(m,n)
输入：非负整数 m, n，其中m与n不全为0 输出：m 与 n 的最大公约数 1. while m>0 do 2. r n mod m 3. n m 4. m r 5. return n
实例：改进的顺序检索
算法1.2 Search(L,x)
课程主要内容
近似算法
随机算法
处理难解问题的策略
问题处理策略计算复杂性理论算法分析方法算法设计技术基础知识
NP 完全理论算法分析与问题的计算复杂性分治动态贪心回溯与策略规划算法分支限界数学基础、数据结构
算法的基本概念
1. 2. 3. 4. 5. 为什么要研究算法？什么是算法？算法化求解问题的过程重要的问题类型算法设计策略
Decrease and conquer Transform and conquer
20
Backtracking and Branch and bound Space and time tradeoffs
求：总等待时间最少的调度方案，即求S的排列i1, i2, …, in使得
min{k 1 ( n k 1)t ik }
n
求解方法 • 贪心策略：加工时间短的先做 • 如何描述这个方法？这个方法是否对所有的实例都能得到最优解？如何证明？这个方法的效率如何？
例2 排序算法的评价已有的排序算法：考察元素比较次数
2-1. 计算判别式d 2-2. 根据d的值进行不同处理 2-2-1:if d>0 x1=… x2=… 2-2-2:if d=0 x1=x2=… 2-2-3:if d<0 ….
4 算法的伪码描述

算法导论读书笔记

算法导论读书笔记【篇一：《算法概论》读书笔记及读后感】《算法概论》读书笔记12计转1 12130907 李酉辰第0章本章较为简短，没有深入系统地涉及某些内容。

主要以fibonacci 数列的例子，让我体会了递归和递推思想的差别。

针对fibonacci数列例子直接递归解法中涉及的重复计算，优化出递推方式，展示了思考问题中自顶向下与自底向上的不同思考角度可能产生较大的算法效率差别，同时隐约体现记忆化搜索的思想。

另外本章较为详细介绍了大o复杂度度量标准。

第1章本章以rsa算法为例，细致深入讨论了rsa算法涉及的相关数论知识，诸如取模运算、模下的四则运算与逆元概念、取模幂运算、素性检测。

在素性检测部分有经典的欧几里德算法、扩展欧几里德算法，同时引入随机化算法概念，以极高的概率保证素性检测有效性。

通过本章的学习，我对过去不曾深入考虑或者说真正考虑的基础性运算有了更深的理解。

之前对乘除运算复杂度总是在以单元操作的概念下以o（1）带过，以后会更加细致地考虑乘除等基本运算的复杂度。

另外，本章以rsa为案例，系统地展示了针对某一问题，如何从基础性知识入手，一步一步学习案例所需基础知识，并将其整合从而解决案例。

素性检测与素因子分解，两个看似相去不远的问题，其复杂性天差地别的现实，从一般角度让人们想到的是类似问题的解决难度可能差别很大仅此而已，而rsa算法展示了如何深入的多想一步，利用这种情况设计出优雅的解决方案。

这思想很值得我借鉴与利用。

第2章本章介绍分治算法思想，提及分治，相信每一个学习算法的人都不会陌生，经典的《算法导论》中就已合并排序为例在开篇不久就引入分治概念。

本书介绍分治的角度与众不同，不似《导论》中总是介绍比较显而易见的可以分治的案例。

本书列举了矩阵相乘、快速傅立叶变换等数学领域分治的应用案例，在这些案例之中，分治的应用很多情况下隐藏的较为深，并非显而易见，加大了分析难度。

但是更能让我感受到分治应用之广泛，可能在学习本章之前，许多类型的题目我不会想到去向分治的角度思考，因为不易看出，但是本章给我的备忘录上加了一条：永远不要忽视分治，针对陌生题目，不要轻易就否决掉往分治角度思考的路线。

算法导论中文版

补充递归和分治策略•通过例子理解递归的概念；•掌握设计有效算法的分治策略；•通过下面的范例学习分治策略设计技巧：过的范例学分策略技¾Merge sort¾Multiplication of two numbers¾Multiplication of two matrices¾Finding Minimum and Maximumj y p¾Majority problem (多数问题)算法总体思想对这k个子问题分别求解。

如果子问题的规模仍然不够z 将要求解的较大规模的问题分割成k个更小规模的子问小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

题。

nT(n)=T(n/2)T(n/2)T(n/2)T(n/2)算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

nT(n)=n/2n/2n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4) T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)T(/4)算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

分治法的设计思想是将个难以直接解决的大问题n T(n)=分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之分而治之。

n/2n/2n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4递归的概念直接或间接地调用自身的算法称为z递归算法。

算法导论学习报告

算法设计与分析学习报告第一部分学习内容归纳“计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。

”（参考文献：百度百科）《算法设计与分析》是一门面向设计，在计算机科学中处于核心地位的课程。

这门课程主要讲授了在计算机应用中经常遇到的问题和求解的方法，分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法复杂性的分析，以及计算理论简介。

第一部分“概论和数学准备”在简单了解了算法的基本概念和复杂性、研究步骤等几个重要知识点后，着重学习了算法的数学基础，包括生成函数、差方方程的求解等，主要适用于求解算法的时间复杂性。

“任何可以用计算机求解的问题所需要的计算时间都与其规模有关：问题的规模越小，解题所需的计算时间往往也越短，从而也就比较容易处理。

”（参考文献：《计算机算法设计与分析（第3版）》）而第二部分介绍的算法常用技术之首——分治法就运用了这样的思想。

分治法的要领在于Divide（子问题的划分）-Conquer（子问题的求解）-Combine（子问题解的组合）。

由于子问题和原问题是同类的，递归的思想在分治法中显得尤其重要，它们经常同时运用在算法设计中。

这部分内容从Select（求第k小元）算法，寻找最近点对算法和快速傅立叶变换FFT等实际应用中深化对分治法思想的理解，同时也强调了平衡思想的重要性。

第三部分“动态规划”与分治法类似，同样是把问题层层分解成规模越来越小的同类型的子问题。

但与分治法不同的是，分治法中的子问题通常是相互独立的，而动态规划法中的子问题很多都是重复的，因此通常采用递推的方法以避免重复计算。

然而，也不是所有的情况下都采用递推法，当有大量的子问题无需求解时，更好的方式是采用动态规划法的变形——备忘录方法。

通常需要用到动态规划法求解的问题都具有子问题的高度重复性和最优子结构性质两大特征，这也是我们分析问题和设计算法时的关键点。

第1讲算法导论讲述

• 什么是算法？ • 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。
广州大学华软软件学院
第3页
算法分析与设计 3
算法(Algorithm)
• 算法是指解决问题的一种方法或一个过程。 • 算法是若干指令的有穷序列，满足性质： • (1)输入：有外部提供的量作为算法的输入。 • (2)输出：算法产生至少一个量作为输出。
lim
n
• 若λ=非零常数，则称Ỹ（n）是T（n）的渐近表达式，或称T（n）渐近等于Ỹ（n），记为 T（n）=Θ（Ỹ（n）），这个记号称为算法运行时间的渐近Θ-记号，简称为Θ-记号。
T ( n)

广州大学华软软件学院
第11页
算法分析与设计 11
5．有效算法
• 如果两个算法运行时间的渐近表达式相同，则将它们视为具有相同时间复杂度的算法。显然，渐近时间为对数幂的算法优于渐近时间为幂函数的算法，而渐近时间为幂函数的算法则优于渐近时间为指数函数的算法。我们把渐近时间为幂函数的算法称为是具有多项式时间的算法，渐近时间不超过多项式的算法则称其为有效的算法。
广州大学华软软件学院
第9页
算法分析与设计 9
3．实例
• 在线性表A中查找。 • （a）查找值为x=1的元素，从A[1]起依次要进行5次检测，第一次找到值为1的元素。 • （b）查找值为x=11的元素，从A[1]起依次检测完所有元素（进行10次检测），没有找到值为11的元素——最坏情形。 • （c）查找值为x=3的元素，从A[1]起仅进行一次检测就找到值为3的元素——最好情形。

算法导论

几种重要的算法一高级技术和分析技术1.动态规划------------------------------------------------------√1.1动态规划的本质动态规划是在20世纪50年代初,为了解决一类多阶段决策问题而诞生的。

那么,什么样的问题被称作多阶段决策问题呢?多阶段决策问题通过下面这个例子来说明。

[例一]多段图中的最短路径问题：在图1.1中找出从Al到D1的最短路径(图中的边上的数字表示该边上的权)。

图1多阶段决策问题这个图有一个特点,就是可以将图中的点分为四类(图1.1中的A、B、C、D)，那么图中所有的边都处于相邻的两类点之间,并且都从前一类点指向后一类点。

这样,图中的边就被分成了三类(A→B、B→C、C→D)。

这时需要从每一类中选出一条边来，组成从Al到Dl的一条路径,并且这条路径是所有这样的路径中的最短者。

这是多阶段决策问题。

更精确的定义如下：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

多阶段决策问题有两个要素：一个是阶段，一个是决策。

1.1.2阶段与状态阶段:将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。

常用字母k表示阶段变量。

阶段是问题的属性。

多阶段决策问题中通常存在着若干个阶段，如上图中就有A、B、C、D这四个阶段。

在一般情况下,阶段是和时间有关的；但是在很多问题中，阶段和时间是无关的。

从阶段的定义中，可以看出阶段的两个特点：一是“相互联系”，二是“次序”。

阶段之间是怎样相互联系的?就是通过状态和状态转移。

状态:各阶段开始时的客观条件叫做状态。

描述各阶段状态的变量称为状态变量，常用Sk表示第k阶段的状态变量，状态变量Sk的取值集合称为状态集合，用Sk表示。

状态是阶段的属性。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。