精华内容
下载资源
问答
  • 算法分析

    千次阅读 2019-12-17 18:01:36
    这篇文章目的是分析算法的复杂度问题,关于算法的定义、特性等等问题在这里不作讲解。 如何度量算法效率 我们知道,算法是解决复杂问题的思路,条条大路通罗马,对于一个复杂的问题,能够解决的算法也有很多种,对于...

    这篇文章目的是分析算法的复杂度问题,关于算法的定义、特性等等问题在这里不作讲解。

    如何度量算法效率

    我们知道,算法是解决复杂问题的思路,条条大路通罗马,对于一个复杂的问题,能够解决的算法也有很多种,对于有多种解决方案的情况,我们当然是想选择一种快速、有效的算法了。那么我们该如何知晓一个算法的效率呢?

    1、事后统计法

    该方法通过设计好的测试程序和数据,然后在计算机中运行,接着对运行时间进行比较,耗时少的效率高。

    但很显然,这种方式有很大缺陷,首先,算法的测试数据需要花时间设计,因为不同的测试数据往往会直接影响运行时间,然后是计算机的硬件也会影响运行时间。这就造成了度量结果的不稳定。

    2、事前分析法

    由此,事前分析法诞生了,该方法无需运行程序,就能够分析出一个算法的效率。

    经过大量分析,前辈们总结出一个算法在计算机上运行时所消耗的时间取决于以下因素:

    1. 算法采用的策略、方法
    2. 编译产生的代码质量
    3. 问题的输入规模
    4. 机器执行指定的速度

    我们抛开第四点,因为第四点是由计算机硬件决定的,我们无法左右。对于一个算法的效率,它的决定因素就是算法的好坏和问题的输入规模。

    通过例子来感受一下:

    void main(){
    	int i,sum = 0,n = 100;
    	for(i = 1;i <= n;i++){
    		sum += i;
    	}
    	printf("%d",sum);
    }
    

    这段代码相信大家都不陌生,这是一个求1到100之间数字和的程序,我们可以来分析一下程序执行的步骤。

    首先,程序执行第一行代码,int i,sum = 0,n = 100;只执行了一次,然后是for循环,循环条件i = 1;i <= n;i++和循环体sum += i;分别执行了n+1次和n次,最后是输出语句printf("%d",sum);,只执行一次。

    执行次数分析出来之后,我们将每句代码的执行次数相加,即:1 + (n + 1) + n + 1 = 2n + 3,这段程序所有代码的执行次数为2n+3次,我们继续看一段程序:

    void main(){
    	int sum = 0,n = 100;
    	sum = (1 + n) * n / 2;
    	printf("%d",sum);
    }
    

    这是刚才求和程序的改进版本,首项加尾项的和乘以项数除以2,即可求出1到100的和,我们来算算这个程序的执行次数。会发现,这段程序中总共三行代码,都只执行了一次,那么总共的执行次数就为3。

    对于事前分析法,我们无需关心实现的语言种类,运行的计算机硬件,忽略循环索引的递增、循环终止条件、变量声明和输出语句等等操作,即可得到一个比较客观的算法效率。

    两个程序对于同一个问题的输入规模是n(输入规模指的是输入量的多少),对于第一个程序,忽略这些因素之后,它的效率为n,第二个程序,它的效率为1。通过比较执行效率不难发现,两个算法的效率相差的不是一点。

    函数的渐进增长

    当然了,算法的效率度量远没有这么简单,我们通过分析来总结一下该如何去计算一个算法的效率。

    首先,我们假设有两个算法,这两个算法的输入规模都为n,而算法1要做2n+3次操作,算法2要做3n+1次操作,你能从操作次数上就判断出哪个算法更高效吗?这其实是办不到的,我们分析一下:

    次数 2n+3 2n 3n+1 3n
    n =1 5 2 4 3
    n = 2 7 4 7 6
    n = 10 23 20 31 30
    n = 100 203 200 301 300

    通过分析发现,当n = 1时,算法1不如算法2,而当n = 2时,算法1和算法2效率相同,按照这个规律,随着n逐渐增大,算法1的效率会逐渐高于算法2。

    此时给出这样的定义,当输入规模n在无限制的情况下,只要超过了一个数值N,这个函数就总是大于另一个函数,我们称函数是渐进增长的。从表格数据中,我们还可以发现,对于常数项,比如2n+3和2n在n的变化下,其函数值并不受影响,所以在计算算法效率的时候可以忽略常数项。

    我们再假设有两个输入规模都为n的算法,算法1要做4n + 8次操作,算法2要做2n2+1次操作,继续分析:

    次数 4n+8 n 2n2+1 n2
    n = 1 12 1 3 1
    n = 2 16 2 9 4
    n = 10 48 10 201 100
    n = 1000 4008 1000 2000001 1000000

    当n = 1时,算法1不如算法2,而当n = 10时,算法1的效率高于算法2,此后,随着n的逐渐增大,算法1的优势越来越明显,我们还能发现,这里除了去掉常数项外,还去掉了与n相乘的常熟,比较n与n2,结论相同。由此可以得出结论,算法效率与最高次项的常数也没有关系。

    我们继续假设有三个输入规模都为n的算法,算法1要做2n2次操作,而算法2要做3n+1次操作,算法3要做2n2+3n+1次操作,继续分析:

    次数 2n2 3n+1 2n2+3n+1
    n = 1 2 4 6
    n = 2 8 7 15
    n = 10 200 31 231
    n = 100 20000 301 20301
    n = 1000 2000000 3001 2003001

    分析发现,随着n的逐渐增大,算法1和算法2的差距逐渐拉大,当n无穷大时,算法1和算法2的效率基本相同,所以得出结论,算法效率与函数中的常数项和其它次要项没有关系,我们只需关注最高次项。

    时间复杂度

    扯了这么多,就是为了引出算法的时间复杂度,在前面的分析中我们得出结论,一个算法,随着输入规模n的增大,它会越来越优于(或者差于)另一算法,这其实就是事前分析法的依据,通过算法时间复杂度来估算算法时间效。那么什么是算法的时间复杂度呢?

    定义:

    在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级,算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随着问题规模n的增大, 算法执行时间的增长率与f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。其中f(n)是问题规模的某个函数。

    这样用大写字母O来体现时间复杂度的方法,我们称之为大O记法。

    如何分析算法的时间复杂度

    如何分析出一个算法的时间复杂度,也叫推导大O阶,其实可以根据上面分析得出的结论:

    1. 用常数1取代程序中的所有加法常数
    2. 只保留最高阶项
    3. 如果最高阶存在且不为1,则去掉与最高阶相乘的常数

    由此得到的结果即为算法的时间复杂度,下面讲解一下比较常见的大O阶:

    1、常数阶

    看下面的程序:

    void main(){
    	int sum = 0,n = 100;
    	sum = (1 + n) * n / 2;
    	printf("%d",sum);
    }
    

    执行次数为3,此时根据结论,用常数1代替所有加法常数,没有最高阶项,所以该算法的时间复杂度为O(1)。

    2、线性阶

    看下面的程序:

    void main(){
    	int i,sum = 0,n = 100;
    	for(i = 1;i <= n;i++){
    		sum += i;
    	}
    	printf("%d",sum);
    }
    

    执行次数为1 + (n + 1) + n + 1 = 2n + 3,根据结论,用常数1代替加法常数,3替换为1;保留最高阶项2n,去除与最高阶项相乘的常数,所以该算法的时间复杂度为O(n)。

    其实在计算的时候,我们无需这样算出每一句代码的执行次数,对于赋值、循环条件、输出语句,我们可以直接不考虑,所以可以直接得出该算法的时间复杂度为O(n)。

    3、对数阶

    看下面的程序:

    void main(){
        int count = 1;
        while(count < n){
            count *= 2;
        }
    }
    

    该程序中我们只需得出循环次数即可求出时间复杂度,由于每次count乘以2之后,就距离n更近了一分,也就是说,有多少个2相乘后大于n,才会退出循环。由2x = n得出x = log2n,所以该算法的时间复杂度为O( logn)。

    4、平方阶

    看下面的程序:

    void main(){
        int i,j,n = 100;
        for(i = 0;i < n;i++){
            for(j = 0;j < n;j++){
                printf("%d\t",n);
            }
        }
    }
    

    我们知道,对于内层循环,其时间复杂度为O(n),而外层循环不过是执行n次内层循环,所以该算法的时间复杂度为O(n2)。

    那么下面这个程序的时间复杂度为多少呢?

    void main(){
        int i,j,n = 100;
        for(i = 0;i < n;i++){
            for(j = i;j < n;j++){
                printf("%d\t",n);
            }
        }
    }
    

    这里修改了一下内层循环,让j = i。分析一下,当i = 0时,内层循环执行n次;当i = 1时,内层循环执行n - 1次;当i = n - 1时,内层循环执行1次。所以总的执行次数为n + (n - 1) + (n - 2) + …… + 1 = (1/2)n^2 + (1/2)n

    根据推导大O阶的结论,保留最高阶项n2/2,去掉相乘的常数1/2,最终算法的时间复杂度为O(n2)。

    5、其它大O阶

    还有一些常见的大O阶在这里就不做详细讲解了,就简单地提一下:

    nlogn阶 O(nlogn)
    立方阶 O(n3)
    指数阶 O(2n)

    常用的时间复杂度所耗费的时间从小到大依次是:

    O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

    算法分析的最坏情况

    在一个算法中,很有可能会出现一些不确定的情况,例如通过循环查找一个数组中的元素,当这个值就是数组的第一个元素时,算法的时间复杂度为O(1),而如果它是最后一个元素,那么时间复杂度为O(n),这也是这个程序中的最坏情况。

    对于所有情况,平均运行时间是最有意义的,然后,一段程序的平均运行时间我们很难通过分析得到,所以一般在没有特殊说明的情况下,求一个算法的时间复杂度都是指求它在最坏情况下的时间复杂度。

    空间复杂度

    随着互联网科技的发展,早先比较贵的存储在如今都较为便宜,所以在某些特定的场景下,可以考虑使用空间来换取时间。

    例如在一个求指定年份是否为闰年的算法中,我们可以事先定义一个有限大的数组,数组下标表示年份,哪一年是闰年,对应的下标元素就为1,此时,如果想判断输入的年份是否为闰年,只需得到该下标的元素值,若为1,则是闰年;若为0,则不是闰年。这样虽然高效,但会加大存储的开销。

    比如排序算法中的基数排序是用空间换取时间的经典算法。

    算法的空间复杂度通过计算算法所需的存储空间实现,空间复杂度的计算公式为:S(n) = O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

    通常情况下,我们更注重算法的时间复杂度,所以,空间复杂度只作为一个了解,不深入讨论。

    展开全文
  • 文章目录1、什么是算法分析2、算法分析专有名词3、渐进算法分析a)、时间复杂度化简规则b)、如何得到算法的增长率c)、两个函数的增长率比较4、渐进算法分析的局限性5、算法分析扩展a)、问题的代价分析b)、空间代价c)...

    本篇文章将要介绍:

    1、什么是算法分析

    要明确算法分析这个概念,就要知道计算机程序设计的两个核心目标:

    1. 程序员角度:设计一种容易理解、编码和调试的算法
    2. 计算机角度:设计一种能有效利用计算机资源的算法

    算法分析就是从计算机角度分析,是对一个算法需要多少计算时间和存储空间作定量的分析。它可以估算出当问题规模变大时,一种算法及实现它的程序的效率和开销,这是一种事前分析估算的方法。

    2、算法分析专有名词

    问题: 需要完成的任务,即一组输入会有想应的输出,可以看出从输入到输出的一个函数。
    算法: 指解决问题的一种方法或一个过程。是对特定问题求解步骤的一种秒数,在计算机中体现为指令的有限序列,其中一条指令表示一个或多个操作。
    算法的四个特性:

    • 正确性: 必须完成期望的功能,因此必须要有输入和输出,并且能够将输入正确地转换为输出。
    • 可行性: 算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。
    • 确定性: 必须无二义性,算法的每一个步骤都必须有明确的定义。
    • 有限性: 步骤一定是有限的,并且执行完成的时间一定是有限的。

    程序: 使用某种程序设计语言对一个算法的实现。
    问题规模: 指的是输入量的数目。
    基本操作: 一个基本操作必须具有这样的性质:完成该操作所需时间与操作数的具体取值无关。
    语句频度: 语句的频度指的是该语句执行的次数。
    算法的代价: 是算法的效率的度量

    • 一个算法如果能在所要求的资源限制内将问题解决好,就说这个算法是有效率的。
    • 分类:
      • 时间代价:需要的时间资源的量
      • 空间代价:需要的空间资源的量
    • 算法代价的度量: 运行时间和所占空间大小。 影响因素:
      • 算法或数据结构的差异
      • 程序的编译和运行环境,如计算机的总线等外部设备,还有机器代码的质量等。需要完成的任务
        增长率: 当输入的规模增长时,算法代价的增长速率。
        T(n): 常表示为算法的时间代价函数,n为输入的规模

    3、渐进算法分析

    渐进算法分析的任务是对设计出的每一个具体的算法,利用数学工具,讨论它的复杂度,探讨具体算法对问题的适应性。探讨当问题输入规模很大或者达到极限的时候,算法代价的变化,是一种事前分析的方法。

    大O表示法: 算法运行时间的上限。 对于非负函数T(n),若存在两个正常数c和n0,使得当n>n0时有T(n)≤cf(n),则称T(n)在集合O(f(n))中,记为T(n)∈O(f(n))。常数n0称为使得上限成立的n的最小值,一般情况下n0取值都很小。通常我们会选择一找到一个最"紧"的上限,因为这样的上限是最贴近算法代价的增长率的。

    大Ω表示法:

    • 类似于大O表示法的定义
      算法运行时间的下限。对于非负函数T(n),若存在两个正常数c和n0,使得当n>n0时有T(n)≥cg(n),则称T(n))在集合Ω(g(n))中,记为T(n)∈Ω(g(n))。同样,通常我们会选择一找到一个最"紧"的下限,因为这样的下限是最贴近算法代价的增长率的。

    • 更严谨的一种定义:
      如果存在正常数c,对无穷多个n使得T(n) ≥ cg(n)成立,则称T(n))在集合Ω(g(n))中,这种定义方式更加严谨,对于一些分段函数,有一部分是无法找到相应的常数的,这是我们需要取复杂度大的那个,用此定义就可以直接找出。

    Θ表示法: 当上、下限相等时,我们就可以用Θ表示法。即如果非负函数T(n)既在O(h(n))中,又在Ω(h(n))中,则称T(n)是Θ(h(n))。这是也说T(n)与h(n)同阶。

    对于一些算法,在相同问题的输入规模下,并不是所有的输入情况的时间复杂度都是相同的,他们往往有以下几种情况:
    最佳情况时间复杂度: 在给定规模时,某个算法在最好的输入情况下算法的时间复杂度。
    最差情况时间复杂度: 在给定规模时,某个算法在最差的输入情况下算法的时间复杂度。
    平均情况时间复杂度: 在给定规模时,算法的"典型"时间代价,即考虑它对于所有可能的输入数据集的代价期望值。(一般为等概率平均,问题遍历每一个数据的概率相同)

    a)、时间复杂度化简规则

    1. 传递性。
      若f(n)∈O(g(n))中,且g(n)在O(h(n))中,则f(n)在O(h(n))中。
    2. 常数系数可忽略。
      若f(n)在O(kg(n))中对于任意常数k>0成立,则f(n)在O(h(n))中; 因为常数系数不会影响时间代价函数的增长率。
    3. 低阶可忽略
      若f1(n) 在O(g1(n))中,f2(n)在O(g2(n))中,则f1(n) +f2(n) 在O( max (g1(n),g2(n) ) ) 中 。
    4. 函数相乘则复杂度相乘
      若若f1(n) 在O(g1(n))中,f2(n)在O(g2(n))中,则f1(n) *f2(n) 在O( g1(n)*g2(n)) 中 。

    b)、如何得到算法的增长率

    方法: 定义估算归纳法

    • 分析问题或算法时,可以求出代价和输入规模的函数T(n),再通过化简规则进行化简即可。如果不能得到T(n)的准确算术表达式,可以用估算和猜测法得到表达式。
    • 利用增长率的上限和下限的定义,采用归纳法,推导出函数的上限和下限。从而得到求解问题的方法或算法增长率的上限和下限。

    c)、两个函数的增长率比较

    如果已知两个函数的增长率的算数表达式,判断哪个增长率更快的方式: 判断两个函数比值的极限lim f(n)/g(n) n-> 无穷

    • 如果极限值趋向于无穷,则f(n)在Ω(g(n))中,因为f(n)增长得更快。
    • 如果极限值趋向于0,则f(n)在O(g(n))中,因为g(n)增长得更快。
    • 如果极限值趋向于非0常数,则f(n)等于θ(g(n)),因为f(n)和g(n)增长率相同。

    4、渐进算法分析的局限性

    • 当数据规模较小时,对估算结果有偏差
    • 增长率相同,无法区分系数不同的情况
    • 对困难问题进行数学建模难得出分析结果

    5、算法分析扩展

    a)、问题的代价分析

    • 问题代价的上限:已知最优解算法的代价上限
    • 问题代价的下限:所有可能算法的代价下限(包括尚未涉及出来的算法)

    b)、空间代价

    • 与分析时间代价类似
    • 渐进分析中增大率的概念对于空间代价同样适用
    • 时间代价是相对于处理某个数据结构算法而言的
    • 空间代价是相对于该数据结构本身而言的

    空间开销: 算法需要的磁盘或内存空间的大小
    空间浪费: 是一个数据结构中预先分配的空间减去当前时机存储的数据,标识空间的利用率
    结构性开销: 是数据结构实现时,为了便于有效地访问而附加的一些信息,这些并非真正数据的附加信息称为结构性开销。使用一些数据结构的结构性开销可以提高对数据结构访问的简单性与有效性,但同时要保证结构性开销尽可能的小。

    c)、空间时间权衡原则

    • 以空间换时间:信息压缩存储
    • 以空间换时间:查找表

    d)、基于磁盘的空间/时间权衡规则

    在磁盘上的存储代价越小,程序运行得越快。这是因为从磁盘上读取数据的时间代价远远大于用于计算的时间代价,于是几乎所有用于对数据进行解压缩的额外操作的时间代价,都小于减少存储代价后节约下来的读盘时间。

    展开全文
  • 并行算法分析

    千次阅读 2018-05-13 16:47:45
    并行算法分析 基本指标 并行算法分析 VS 串行算法分析 并行程序设计的复杂性 并行算法的额外开销 性能评价标准 效率 代价 可扩展性 并行算法分析 基本指标 并行算法分析 VS 串行算法分析 串行算法...

    并行算法分析

    基本指标

    并行算法分析 VS 串行算法分析

    1. 串行算法评价:算法时间复杂度表示为输入规模的函数
    2. 并行算法评价:除了输入规模之外,还应考虑处理器数目、**处理器相对运算速
      通信速度**
    3. 评价标准
      • 运行时间
      • 加速比:并行算法比串行算法快多少?

    并行程序设计的复杂性

    1. 足够的并发度(Amdahl定律)
    2. 并发粒度
      独立的计算任务的大小
    3. 局部性
      对临近的数据进行计算
    4. 负载均衡
      处理器的工作量相近
    5. 协调和同步
      谁负责?处理频率?

    并行算法的额外开销

    除了串行算法要做的之外的工作
    1. 进程间通信:最大开销,大部分并行算法都需要
    2. 进程空闲:负载不均、同步操作、不能并行 化的部分
    3. 额外计算

    • 最优串行算法难以并行化,将很差的串行算法并行化,并行算法计算量>最优串行算法

    • 最优串行算法并行化也会产生额外计算:并行快 速傅立叶变换,旋转因子的重复计算

    性能评价标准

    1. 运行时间
      串行算法:TS,算法开始到结束的时间流逝
      并行算法:TP,并行算法开始到最后一个进 程结束所经历时间

    2. 并行算法总额外开销
      To=pTP – TS

    3. 加速比
      S=TS/TP

    效率

    • 理想并行算法,S=p
    • 难实现,不是100%时间都用于有效计算
    • 求和例子,部分时间处理器处于空闲
    • 效率(Efficiency):度量有效计算时间
    • 理想情况=1,正常0~1
    • E=S/p
    • 求和例子
      E= Q(n/logn)/n= Q(1/logn)

    代价

    • cost,并行算法运行时间×处理器数量
    • 所有处理器用来求解问题的时间总和
    • E=TS/cost,p=1时,cost=TS
    • 代价最优,cost-optimal:代价与最优串 行算法运行时间渐进相等——E= Q(1)
    • 代价也称为工作量(work),处理器时 间积(processor-time product)

    可扩展性

    可扩展性是高性能并行机和并行算法追求的主要目标,其主要作用:
    ❑ 度量并行系统性能的方法之一
    ❑ 度量并行体系结构在不同系统规模下的并行
    处理能力
    ❑ 度量并行算法内在的并行性
    ❑ 利用系统规模和问题规模已知的并行系统性 能来预测规模增大后的性能:scale down,
    适合开发、调试,不适合性能预测

    展开全文
  • 大学算法分析与设计复习总结

    万次阅读 多人点赞 2013-06-08 11:49:20
    大学算法分析与设计复习总结 为了拿大学的那悲剧的学分,好好弄懂以下所有知识点吧。把老师的复习的提纲,特意汇总了所有考点,方便童鞋们复习。不喜勿喷!!! 这本书是《算法设计与分析》 王红梅 编著 一共...

    大学算法分析与设计复习总结


    为了拿大学的那悲剧的学分,好好弄懂以下所有知识点吧。把老师的复习的提纲,特意汇总了所有考点,方便童鞋们复习。不喜勿喷!!!

    这本书是《算法设计与分析》 王红梅 编著

    一共有以下12章,我们学了1、3、4、5、6、7、8、9

    分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法



    第1章 绪论

    考点:

    1、  算法的5个重要特性。(P3)

    答:输入、输出、有穷性、确定性、可行性

    2、  描述算法的四种方法分别是什么,有什么优缺点。(P4)

    答:

    1.      自然语言 优点:容易理解;缺点:容易出现二义性,并且算法都很冗长。

    2.      流程图       优点:直观易懂;缺点:严密性不如程序语言,灵活性不如自然语言。

    3.      程序设计语言 优点:用程序语言描述的算法能由计算机直接执行;缺点:抽象性差,是算法设计者拘泥于描述算法的具体细节,忽略了“好”算法和正确逻辑的重要性,此外,还要求算法设计者掌握程序设计语言及其编程技巧。

    伪代码    优点:表达能力强,抽象性强,容易理解

     

    3、  了解非递归算法的时间复杂性分析。(P13)

     要点:对非递归算法时间复杂性的分析,关键是建立一个代表算法运行时间的求和表达式,然后用渐进符号表示这个求和表达式。

    非递归算法分析的一般步骤是:

    (1)      决定用哪个(或哪些)参数作为算法问题规模的度量。

    (2)      找出算法的基本语句。

    (3)      检查基本语句的执行次数是否只依赖问题规模。

    (4)      建立基本语句执行次数的求和表达式。

    (5)      用渐进符号表示这个求和表达式。

    [例1.4]:求数组最小值算法

     int ArrayMin(int a[ ], int n)

     {

          min=a[0];

          for (i=1; i<n; i++)

             if (a[i]<min) min=a[i];

          return min;

     }

    问题规模:n

    基本语句: a[i]<min

    T(n)= n-1=O(n)

     

    4、  掌握扩展递归技术和通用分治递推式的使用。(P15)

    扩展递归技术:






    通用分支递归式:

     



    5、  习题1-4,习题1-7

    设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求给出伪代码描述,并用一组例子进行跟踪验证,写出验证过程。

    (1)伪代码

    1.   令最小距离min等于数组头两个元素R[0]和R[1]的差的绝对值;

    2.   从i=0循环至i<n-1,对于每个R[i]

    2.1     分别求其与j=i+1至j<n的数的差的绝对值;

    2.2     如果此值小于最小距离,则令新的最小距离为此值;

    3.   输出最小距离。

    (2)用实例进行跟踪验证

    R[6]={10,5,11,16,30,14},n=6;

    Min=|10-5|=5;

    i=0,j=1, |R[i]-R[j]|=|10-5|=5;

       j=2,|R[i]-R[j]|=|10-11|=1<min;min=1;

       j=3, |R[i]-R[j]|=|10-16|=6;

       j=4, |R[i]-R[j]|=|10-30|=20;

       j=5, |R[i]-R[j]|=|10-14|=4;

    i=1,j=2, |R[i]-R[j]|=|5-11|=6;

       j=3, |R[i]-R[j]|=|5-16|=11;

       j=4, |R[i]-R[j]|=|5-30|=15;

       j=5, |R[i]-R[j]|=|5-14|=9;

    i=2,j=3, |R[i]-R[j]|=|11-16|=5;

       j=4, |R[i]-R[j]|=|11-30|=19;

       j=5, |R[i]-R[j]|=|11-14|=3;

    i=3,j=4, |R[i]-R[j]|=|16-30|=14;

       j=5, |R[i]-R[j]|=|16-14|=2;

    i=4,j=5, |R[i]-R[j]|=|30-14|=16;

    最后输出min=1


    7、使用扩展递归技术求解下列递推关系式

    (1)



    (2)




    第3章 蛮力法

    1、  掌握蛮力法的设计思想:

    蛮力法依赖的基本技术——扫描技术,即采用一定的策略将待求解问题的所有元素依次处理一次,从而找出问题的解;

    关键——依次处理所有元素。

     

    2、  蛮力法的代表算法及其时间复杂度:

    顺序查找,O(n)

    串匹配(BF O(n*m) ,KMPO(n+m) , BMO(n*m)

    选择排序,O(n2)

    冒泡排序,O(n2)

    生成排列对象(排列问题),O(n!)

    生成子集(组合问题),O(2n)

    0/1背包 属于组合问题。

    任务分配,哈密顿回路,TSP问题 属于排列问题。

    最近对问题 O(n2),凸包问题 O(n3)

    3、  掌握BF和KMP算法的原理,能够画出比较过程。P71习题3的4。要求给出一串字符串,能够求出对应的next数组,并能使用KMP算法进行比较匹配。

    4、  掌握选择排序和冒泡排序算法描述和时间复杂性,要求能够写出伪代码。(P56-58)

    选择排序

    算法描述:选择排序开始的时候,扫描整个序列,找到整个序列的最小记录和序列中的第一记录交换,从而将最小记录放到它在有序区的最终位置上,然后再从第二个记录开始扫描序列,找到n-1个序列中的最小记录,再和第二个记录交换位置。一般地,第i趟排序从第i个记录开始扫描序列,在n-i+1个记录中找到关键码最小的记录,并和第i个记录交换作为有序序列的第i个记录。

    时间复杂性:O(n2)

    伪代码:

     

    冒泡排序

    算法描述:冒泡排序开始的时候扫描整个序列,在扫描过程中两两比较相邻记录,如果反序则交换,最终,最大记录就能被“沉到”了序列的最后一个位置,第二趟扫描将第二大记录“沉到”了倒数第二个位置,重复上述操作,直到n-1趟扫描后,整个序列就排好序了。

    冒泡排序,O(n2)


    5、  算法设计题:习题3-3,3-6,3-8,3-11,3-13

    3-3 对于KMP算法中求next数组问题,设计一个蛮力算法,并分析其时间性能。

    voidGetNext(char T[ ], int next[ ])
    {
       next[1]=0;
       next[2]=1;
       j=T[0],k=0;
       for(;j>2;j--){
            for(n=j-2;n>=1;n--){//n为要比较的前缀的最后一个字符的下标
                   m=j-n;//m为要比较的后缀的第一个字符的下标
                   for(i=1;i<=n;i++)
                   {
                           if(T[i]!=T[m+i-1])break;
                   }
                   if(i==n+1){next[j]=n+1;break;}
             }
            if(n==0)next[j]=1;
             }
    }


    3-4 假设在文本“ababcabccabccacbab”中查找模式 “abccac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。



    由此可知,用BF算法一共要进行3+1+4+1+1+6+1+1+1+6=25次比较方能匹配出

     

    KMP算法:next[]={,0,1,1,1,1,2};


    由此可知,用KMP算法一共要进行3+4+6+5=18次比较方能匹配出

     

    参考代码如下:

    排列最终存储在长度为n的阶乘,元素类型为指针的数组中,数组指向一个排列,具体的排列数据存储在数组中。

     

    int fabs(int n)
    {
           int r=1;
           for(inti=n;i>1;i--)
                  r=r*i;
           return r;
     
    }
     
    //排列存储在数组中
    void getArrangement(int**&s,int n)
    {
           int * p,*q;
           int * *s1;
           int i,j,k,l,m,o;
           s=new int *[1];
           s[0]=newint[1];
           s[0][0]=1;
           for(i=2;i<=n;i++)
                  {
                         j=0;
                         o=0;
                         m=fabs(i-1);
                         s1=newint *[fabs(i)];
                         while(o<m)
                         {
                                q=p=s[o];
                                for(k=i-1;k>=0;k--)
                                {                                 
                                       s1[j]=newint[i];
                                       for(l=0;l<i;l++)
                                       {
                                              if(l==k){s1[j][l]=i;}
                                              else{
                                                     s1[j][l]=*p;
                                                     p++;}
                                       }
                                       j++;
                                       p=q;
                                }
                                o++;
                                delete[] q;
                         }
                         delete[]s;
                         s=s1;
                  }
    }

     

    3-8对于一个平面上n个点的集合S,设计蛮力算法求集合S的凸包的一个极点。

    点集合中最左边或者最右边的点一定是凸包的一个极点,则求凸包的极点的问题转化为求点的x坐标最大或最小的点

    int getPole(int x[],int y[],int n)
    {
           int r=0;
           for(inti=0;i<n;i++)
           {
                  if(x[i]>x[r])r=i;
           }
           return r;
    } 

    3-11 设计算法生成在n个元素中包含k个元素的所有组合对象。

    两种思路:

    1、  生成所有的组合,在组合中找元素个数为k个的组合。

    伪代码:

    1.初始化一个长度为n的比特串s=00…0并将对应的子集输出;

     2.for(i=1; i<2n; i++)   //注意不能书写成i<=2n

        2.1  s++;

        2.2  判断s中1的个数,若为k,则将s对应的子集输出;

     

    2、  使用k层嵌套循环生成元素个数为k个的组合。

    设k=3;n个元素存储在数组a[]中;

    伪代码:

    for (i=1; i<n-2; i++)

    for(j=i+1; i<n-1; i++)

    for(k=j+1; i<n; i++)

          输出a[i]a[j]a[k]构成的组合。

     

    3-13美国有个连锁店叫7-11这个连锁店以前是每天7点开门,晚上11点关门

    不过现在是全天24小时营业。有一天,有个人来到这个连锁店,买了4件商品

    营业员拿起计算器敲了一下,说:总共是$7.11顾客开玩笑说:所以你们商店就叫7-11?营业员没有理她,说:当然不是,我是把它们的价格相乘之后得到的。

    顾客说:相乘?你应该把他相加才对。营业员说,我弄错了。接着又算了一遍,结果让两个人吃惊的是:计算结果也是$7.11请问,这4件商品的价格是多少?

    参考代码:

    #include<iostream.h>
    #include <stdio.h>
    int main()
    {
    long i,j,k,m;
     
    for (i=1; i <=711/4 ; i++)
    {
    for (j=i; j <=711/3 ; j++)
    {
    for (k=j; k <=711/2 ; k++)
    {
    m=711-i-j-k;
    if (i*j*k*m==711*1000000)
    {
    cout<<i<<endl<<j<<endl<<k<<endl<<m<<endl;
                }
    }
    }
    }
    return 0;
    }

    输出结果为:价格分别是1.2   1.25   1.5     3.16


    第4章  分治法

    了解分治法的设计思想

    设计思想:将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。

    步骤:(1)划分(2)求解子问题(3)合并

     

    分治法的代表算法及时间复杂度:

    归并排序,快速排序,最大子段和,最近对问题,凸包问题,这五种问题的分治算法的时间复杂度为O(nlog2n)

    棋盘覆盖,循环赛日程安排为O(4k)

     

    掌握归并排序和快速排序算法的算法伪代码。(P78-83)

    归并排序:


    算法中数组r中存储原始数据,r1在中间过程中存储排序后的数据,s指需排序数组的起始下标,t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。


    快速排序:



    掌握最大子段和问题的算法伪代码。(P83-85)



    对于待排序列(5, 3, 1, 9, 8, 2, 4, 7),画出快速排序的递归运行轨迹。

    按升序排列

    初始序列:5,3,1,9,8,2,4,7

    第一次划分:4,3,1,2,5,8,9,7

    第二次划分:2,3,1,4,5,8,9,7

    第三次划分:1,2,3,4,5,8,9,7

    第四次划分:1,2,3,4,5,7,8,9

    排序完成,红色字体为每次划分的轴值

     

    在有序序列9(r1,r2,```, rn)中,存在序号i ( 1<=i<=n),使得ri = i, 请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O(log2n).

    参考代码:

    #include<iostream.h>
    int findr(ints[],int begin,int end)
    {
           if(begin==end){
                  if(s[begin]==begin) return begin;
                  else return 0;
           }else
           {
                  int m=(begin+end)/2;
                  if(s[m]>m) return findr(s,begin,m-1);
                  else if (s[m]==m)return m;
                  else return findr(s,m+1,end);
           }
     
    }
    void main()
    {
           int s[]={0,1,1,2,4,6,8};
           cout<<findr(s,1,6)<<endl;
    }
    

    第5章 减治法

    了解减治法的设计思想

    设计思想:原问题的解只存在于其中一个较小规模的子问题中,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。

     

    掌握使用减治法的代表问题及时间复杂度:

    折半查找,二叉树查找,堆排序,选择问题,淘汰赛冠军问题,假币问题;

    以上问题的时间复杂度,如果减治是每次减小为原来规模的1/2,则时间复杂度一般为O(log2n)

     

    掌握折半查找的算法伪代码描述及具体例子的查找过程,会根据折半查找的过程创建判定树。(P98-100)


    会根据已知数据序列创建一个二叉查找树。(P100)


    掌握堆排序算法中的两种调整堆和新建堆的方法:筛选法和插入法(P101-105)

    堆调整问题:将一个无序序列调整为堆

    (1)筛选法调整堆

            关键问题:完全二叉树中,根结点的左右子树均是堆,如何调整根结点,使整个完全二叉树成为一个堆?    

    (2)插入法调整堆

    关键问题是:在堆中插入一个结点,如何调整被插入结点,使整个完全二叉树仍然是一个堆?


    掌握选择问题的算法的伪代码(P105-106)

     

     

    习题5-1,算法设计题

    习题5-4,给出任意一组数据,能分别用筛选法和插入法写出创建堆的过程,并用两种方法进行堆排序。

    对(47,5,26,28,10)进行筛选堆排序,使用大根堆,形成升序 ,列出每次筛选后的序列

    形成大根堆的过程(先把数组直接表示成完全二叉树):

    47,5,26,28,10(叶子结点,不用筛选)

    47,5,26,28,10 (叶子结点,不用筛选)

    47,5,26,28,10 (叶子结点,不用筛选)

    47,5,26,28,10

    47,28,26,5,10 (5与两个孩子中的大者比较,5小,交换位置)

    47,28,26,5,10 (47与两个孩子中的大者比较,47大,不用交换位置)

    47,28, 26, 5 ,10 (大根堆)

    10,28, 26, 5 , 47 (取出堆顶元素后的序列)

    10,28, 26, 5 , 47 (筛选)

    28, 10 , 26, 5 , 47

    28, 10 , 26, 5 , 47 (大根堆)

    5, 10 , 26, 28, 47 (取出堆顶元素后的序列)

    5, 10 , 26, 28, 47 (筛选)

    26, 10 , 5, 28, 47

    26, 10 , 5, 28, 47 (大根堆)

    5, 10 , 26, 28, 47 (取出堆顶元素后的序列)

    5, 10 , 26, 28, 47 (筛选)

    10, 5 , 26, 28, 47

    10, 5 , 26, 28, 47 (大根堆)

    5, 10 , 26, 28, 47 (取出堆顶元素后只剩一个值,结束算法)

    对(47,5,26,28,10)进行插入法生成大根堆

    47

    47 5

    47 5 26

    47 28 26 5

    47 28 26 5 10


    第6章 动态规划法

    了解动态规划法的设计思想

    设计思想:将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解。

    步骤:

    将原始问题分解为相互重叠的子问题,确定动态规划函数;

    求解子问题,填表;

    根据表,自底向上计算出原问题的解。

     

    掌握可以用动态规划法解决的问题及时间复杂度:

    TSP,多段图的最短路径问题,0/1背包,最长公共子序列问题,最优二叉查找树,近似串匹配问题;

    多段图的最短路径问题: O(n+m)

    0/1背包问题: O(n×C)

     

    掌握多段图的最短路径问题的动态规划算法及具体实现(P121-123),习题6-2



    动态规划函数为:

    cost[i]中存储顶点i到终点的最短路径长度

    cost[i]=min{C[i][j]+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点)

    path[i]=使C[i][j]+cost[j]最小的j

    先构造cost数组和path数组

     

    掌握0/1背包问题的动态规划算法及具体实现(P123-126),习题6-3


     

    例题:用动态规划法求如下0/1背包问题的最优解:有5个物品,其重量分别为(3,2,1,4,5),物品的价值分别为(25,20,15,40, 50),背包容量为6。写出求解过程。

    0/1背包问题的动态规划函数为:


    V(i,j)表示把前i个物品放入容量为j的背包中的最大价值和。

    填表过程:



    放入背包中的物品的求解过程:
    则65表示把5个物品放入容量为6的背包中的最大价值和。

    i=5,j=6;  v[5][6]>v[4][6],x[5]=1, j=6-w[5]=1

    i=4,j=1; v[4][1]=v[3][1], x[4]=0

    i=3,j=1; v[3][1]>v[2][1], x[3]=1, j=1-w[3]=0

    i=2,j=0; v[2][1]=v[1][0], x[2]=0

    i=1,j=0; v[1][0]=v[0][0], x[1]=0

    结果是把第3个和第5个放入了背包

    掌握最长公共子序列问题的动态规划法算法及具体实现(P126-128),习题6-4

     

    求X=“xzyzzyx”和Y=“zxyyzxz”序列的最长公共子序列的动态规划函数为:


    L[i][j]表示X中前i个元素和Y中前j个元素构成的序列的最长公共子序列的长度。

    为了确定具体的最长公共子序列,需要同时计算S[i][j]的值,S[i][j]表示在计算L[i][j]的过程中的搜索状态。



     


    子序列为斜箭头所标示的行或列:X[2],X[3],X[6] ,X[7]或Y[1], Y[3], Y[4] , Y[6]
    最长公共子序列的长度为4

    即为:zyyx




     

    第7章 贪心法

    了解贪心法的设计思想

     

    贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出局部最优选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。

    贪心法的关键在于决定贪心策略。

     

    掌握可以用贪心法解决的问题:

    TSP问题中的两种解决方法:最近领点策略,最短链接策略

    最小生成树问题的两种算法:最近顶点策略(Prim算法),最短边策略(Kruskal算法)

    背包问题,活动安排问题,多机调度问题,哈夫曼编码。

     

    掌握最小生成树的两种贪心算法:prim算法和kruskal算法(P145-148),给出具体的例子,能够用两种方法画出树的生成过程。


     

    掌握背包问题的贪心算法(P148-151),给出一个具体的例子,能够写出解决问题的过程。习题7-2

    问题:求如下背包问题的最优解:有7个物品,价值P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量W=15.

    解决方法:

    先对物品的单位重量价值按照降序排列

    物品重量

    物品价值

    物品价值/物品重量

    1

    6

    6

    2

    10

    5

    4

    18

    4.5

    5

    15

    3

    1

    3

    3

    3

    5

    1.67

    7

    7

    1

    依次把物品放入容量为15的背包,直到背包被装满

    1+2+4+5+1=13,前5个物品装入背包,还剩下容量为2,第6个物品只能装入2/3

    所以总价值为:6+10+18+15+3+5*2/3=55.3333

     

    给出字符集和对应的频率,能够画出对应的哈夫曼树,并对给定的字符串进行哈夫曼编码。(P155-157)



    第8章 回溯法

    了解回溯法的设计思想

    设计思想:从解空间树根结点出发,按照深度优先策略遍历解空间树,在搜索至树中任一结点时,先判断该结点对应的部分解是否满足约束条件,或者是否超出目标函数的界,也就是判断该结点是否包含问题的(最优)解,如果肯定不包含,则跳过对以该结点为根的子树的搜索,即所谓剪枝(Pruning);否则,进入以该结点为根的子树,继续按照深度优先策略搜索。直到搜索到叶子结点,则得到问题的一个可能解。

    步骤:

    确定解向量和分量的取值范围,构造解空间树;

    确定剪枝函数;

    对解空间树按深度优先搜索,搜索过程中剪枝;

    从所有的可能解中确定最优解。

     

    了解可以用回溯法解决的问题:

    属于组合问题和排列问题中求最优解的问题都可以用回溯法解决,例如:图着色问题,哈密顿回路问题,八皇后问题(4皇后问题),批处理作业调度问题。

     

    掌握m颜色图着色判定问题的回溯法算法,并能画出解空间树的搜索过程(P168-170),习题8-4

    对图8.14使用回溯法求解图问题,画出生成的搜索空间。


    解:图着色问题求解的是满足图着色要求的最小颜色数。对图8.14应该从1、2、3、4……种颜色依次尝试用回溯法判定是否满足M着色的要求。

    经搜索,1种和2种颜色均不能满足图着色的要求,3种颜色可以满足图着色要求,搜索过程如下,所以图8.14的着色的最少颜色数应该为3

    搜索空间为:

     

    掌握n皇后问题的回溯法算法,并能画出解空间树的搜索过程(P173-174),

    自己看书

    掌握0/1背包问题的回溯算法,并能画出解空间树的搜索过程(P163-164),习题8-5

    自己看书

    习题8-6,算法设计题。

     给定一个正整数集合X={x1,x2,…, xn}和一个正整数y,设计回溯算法,求集合X的一个子集Y,使得Y中元素之和等于y。

    解:

    用回溯法求解问题分析:

    该问题为求子集问题。

    解分量的和小于y为剪枝函数。

    当搜索到结点,并且解分量的和等于y时,找到问题的解。

     

    1.X={x1,x2,x3……xn },sum=0,Y={ }为解向量,初始化为全0;

    2.flag=false;

    3.k=1;

    4.while (k>=1)

          4.1 当(Sk取1、0)循环执行下列操作

                4.1.1yk=Sk中的下一个元素;

                4.1.2将yk加入Y;

                4.1.3sum=+(yk?xk:0);

                4.1.4if (sum==y) flag=true; 转步骤5;

                4.1.4else if (sum<y) k=k+1; 转步骤4;

          4.2 重置Sk,使得下一个元素排在第1位;

          4.3 k=k-1;    //回溯

    5.if flag 输出解Y;

          else 输出“无解”;

    参考代码:

    #include <iostream.h>
    const int N=5;
    int f(int x[],int  y[],int n)
    {
         //初始化y,y为所求的集合
         for(inti=0;i<N;i++)
             y[i]=2;
         int k=0;
         int sum=0;
         while(k>=0)
         {
             y[k]=y[k]-1;
             if((y[k]==1||y[k]==0)&&k<N){
                  sum=sum+(y[k]?x[k]:0);
                  if(sum==n){break;}//找到解
                  else{
                       if(sum<n){k++;}//搜索下一个
                       else{
                           sum=sum-(y[k]?x[k]:0);
                       }
                  }
             }
             else{//回溯
             //  sum=sum-(y[k]?x[k]:0);
                  y[k]=2;
                  k--;
                  sum=sum-(y[k]?x[k]:0);
             }
         }
         return k;
    }
     
    void main()
    {
         int x[N]={2,1,3,4,2};
         int y[N]; //解向量
         int n=12; //题目要求等于的和
         int k=f(x,y,n);//k表示搜索到第几个元素
         cout<<k<<endl;
         for(int i=0;i<N;i++)
             cout<<(y[i]==1?x[i]:0)<<endl;
     
    }


    第9章 分治限界法

    了解分支限界法的设计思想

    设计思想:

    1)首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up] ,并确定限界函数;

    2)然后按照广度优先策略遍历问题的解空间树,在分支结点上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的限界函数的可能取值;

    3)如果某孩子结点的限界函数可能取得的值超出目标函数的界,则将其丢弃;否则,将其加入待处理结点表(以下简称表PT)中;

    4)依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点;

    5)重复上述过程,直到找到搜索到叶子结点,如果叶子结点的限界函数的值是极值,则就是问题的最优解,否则,找到其他极值结点重复扩展搜索。

    步骤:

    确定解空间树

    确定限界函数

    按广度优先搜索解空间树,计算限界函数的值,填入PT表

    从PT表中寻找极值,继续扩展结点,直到找到限界函数值为极值的叶子结点。

     

    了解可以使用分支限界法解决的问题:

    TSP问题,多段图的最短路径问题,任务分配问题,批处理作业调度问题,0/1背包问题。

    掌握任务分配问题的分支限界法(P195-197),习题9-5

    掌握0/1背包问题的分支限界法(P184-185),习题9-6

    掌握批处理作业问题的分支限界法(P198-200),习题9-7


    展开全文
  • 算法和算法分析总结

    千次阅读 2017-07-26 22:01:15
    算法和算法分析总结 算法:是对特定问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。 算法的5个特性: (1)有穷性:一个算法总是(对于任何合法的输入值)在执行有穷步之后结束,且...
  • 算法分析与优化

    千次阅读 2019-12-29 20:26:56
    算法分析 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率.算法分析的目的在于选择合适算法和改进算法.一个算法的评价主要从时间复杂度和空间复杂度来考虑. 1、时间复杂度 (1)时间频度 ...
  • 算法分析初步

    千次阅读 2016-05-09 02:19:50
    算法分析 2016年5月9日 1:15 主要包括 对时空复杂度的分析 ,还有算法的实际运行性能及算法可视化。   步骤: 1.量化算法的实际运行性能   选择衡量算法实际性能的量化指标是他的实际运行时间...
  • AKAZE算法分析

    万次阅读 多人点赞 2018-03-16 19:57:53
     局部特征相关算法在过去二十年期间风靡一时,其中代表的有SIFT、SURF算法等(广泛应用于目标检测、识别、匹配定位中),这两种算法是用金字塔策略构建高斯尺度空间(SURF算法采用框滤波来近似高斯函数)。不论SIFT还是...
  • 前言都说数据结构与算法分析是程序员的内功,想要理解计算机世界就不能不懂点数据结构与算法,然而这也备受争议,因为大多数的业务需求都用不上数据结构与算法,又或者说已经有封装好的库可以直接调用,例如Java中的...
  • RMQ算法分析

    万次阅读 多人点赞 2014-08-06 18:48:20
    RMQ算法,是一个快速求区间最值的离线算法,预处理时间复杂度O(n*log(n)),查询O(1),所以是...算法分析:这个算法就是基于DP和位运算符,我们用dp【i】【j】表示从第 i 位开始,到第 i + 2^j 位的最大值或者最小值。
  • 斐波那契数列算法分析

    万次阅读 2018-08-13 12:50:47
    斐波那契数列算法分析 背景: 假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去。每只
  • 《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...
  • DWA算法分析

    万次阅读 多人点赞 2019-08-17 13:39:47
    机器人在获得目的地信息后,首先经过全局路径规划规划出一条大致可行的路线,然后调用局部路径规划器根据这条路线及costmap的信息规划出机器人在局部时做出具体行动策略,ROS中主要是使用了DWA算法。在ROS中每当...
  • 什么是算法分析

    千次阅读 2018-03-10 14:45:47
    第二:算法分析常见的函数中,线性算法效率最高。第三:当N足够大时,函数的增长率是最重要的。第四:平方算法对输入规模超过几千是不可行的。第五:立方算法对输入规模是几百不可行的。第六:按增长率升序排列的...
  • C语言素数判断算法分析

    千次阅读 2019-11-08 16:41:07
    C语言素数判断算法分析 1、素数的定义 素数:也叫质数,是指大于1,且只能被1和它自身整除的自然数; 1既不是素数,也不是合数; 2是最小的素数; 2、三种算法分析 2.1 最简单最易懂的判断方法 2,3是...
  • Python算法分析与设计:最大流算法

    千次阅读 2019-02-01 14:30:03
    Python算法分析与设计:最大流算法 一、实验目的 1、掌握最大流问题的定义,了解流量、容量以及他们之间的关系。 2、掌握通过增广路径求最大流问题的Forder-Fulkerson和Edmond-Karp算法,理解这两个算法之间的异同 3...
  • js实现扫雷-算法分析

    千次阅读 2018-11-21 15:21:59
    本文主要是通过使用Javascript,通过对扫雷游戏中用到的算法分析,一步步实现用到的算法,进而实现扫雷过程,本文没有对实际游戏进行完善,主要是针对于算法分析,帮助小伙伴应对免试或者求职时遇到的算法;
  • 京东sign 在APP中的 算法分析

    千次阅读 2021-04-18 15:07:03
    京东sign 在APP中的 算法分析 京东APP中,为了校验请求的完整性,大部分请求的url中都带了一个 sign参数,下面是一个Android客户端APP请求的抓包信息: 通过工具反编译后分析java源码后发现,每个sign都需要5个参数...
  • 数据结构与算法分析 Java语言描述第2版

    千次下载 热门讨论 2013-04-11 17:38:12
    中文名: 数据结构与算法分析_Java语言描述(第2版) 作者: 韦斯 译者: 冯舜玺 图书分类: 软件 资源格式: PDF 版本: 扫描版 出版社: 机械工业出版社 书号: ISBN:9787111231837 发行时间: 2009年01月01日 地区...
  • 一步步学算法(算法分析)---6(贪心算法)

    千次阅读 多人点赞 2013-09-29 18:45:08
    这个总结的很详细。在学习过程中帮了我很大的忙...参考资料 《算法分析与设计》 王晓东编著 (在排版过程做了些改动。还望见谅) 贪心算法 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法
  • 前面对算法分析的一些常用的 渐进符号 做了简单的描述,这里将使用归并排序算法做为一个实战演练。 这里首先假设读者对归并排序已经有了简单的了解(如果不了解的同学可以自行百度下归并排序的原理)。了解此算法...
  • 这篇小文简单记录了自己的一个小小发现,也就是勒贝格积分和算法分析方法上的一个等同点:其实现在我已经比以前更清楚的看到计算机科学与数学中的相贯通的地方,这也是我看了《算法导论》《具体数学》的部分内容后才...
  • 排序算法(1)插入排序的算法分析

    千次阅读 2016-07-25 23:11:22
    算法分析 算法伪代码 图示分析 算法复杂度分析 导语 今天,我们介绍的是排序算法经典的一种排序算法,这个算法是插入排序。 相信大家都玩过纸牌。插入排序的工作方式就像许多人排序一手扑克牌。 ...
  • DQN算法分析

    万次阅读 多人点赞 2017-07-31 20:43:30
    分析了DeepMind在2013年和2015 年提出的深度增强算法
  • 本博文主要分析了基于传统计算机视觉的细胞分割算法和基于深度学习的细胞分割算法。... 医学影像分割——细胞分割算法分析与总结 1. 基于传统算法的细胞分割总结 1.1几种常用二值化方法 1.1.1 全局二...
  • DCM姿态估计算法分析

    千次阅读 2017-02-15 20:22:16
    DCM姿态估计算法分析飞控算法 以下内容主要是阅读Direction Cosine Matrix IMU: Theory (by William Premerlani and Paul Bizard)写成的内容整理,只是用来自己看的,所以多有省略,详细的请参见原文。 英文原版...
  • 本文主要讲讲简单的递推方程来求解算法的时间复杂度 文章目录1. 递推方程的引入1.1 插入排序时间复杂度求解1.2 二分归并排序时间复杂度求解2 总结 1. 递推方程的引入 汉诺塔问题大家都知道,现在以汉诺塔问题来引入...
  • 数据结构与算法分析算法分析

    千次阅读 2018-09-21 21:17:54
     如果一个算法常用常数时间将问题的大小消减为其一部分,那么该算法就是   如果使用常数时间把问题减少一个常数,那么该算法就是      对分查找:  循环在High-Low=N-1开始,在High-Low>=-1时...
  • 算法分析与设计|主要内容整理

    千次阅读 多人点赞 2020-06-16 19:51:46
    相对本科的算法学习,老师让我们从今日份考试中感受到算法分析与设计的重要,而不只是再停留在会做做题的阶段。 上一周的复习很充实,看算法与看论文调代码做PPT交织着hhh,觉得也许复习的意义在于做一个全面梳理...
  • 横向控制算法分析

    千次阅读 2020-03-13 15:50:51
    跟踪算法介绍与分析

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 183,975
精华内容 73,590
关键字:

算法分析