精华内容
下载资源
问答
  • 基本概念 一.算法定义 算法就是一个由有限的指令集组成的过程。从可能的输入集中给这个过程一个输入,如果系统地执行该指令集,那么对于这个特定地输入,当输出存在时,就能得到输出;当没有输出时,就什么结果也...

    在学习算法的过程中始终离不开三个问题:

    1.如何找到一个有效的算法去解决问题;

    2.对于解决同样的问题,如何比较不同的算法;

    3.如何判断算法的优点。

     基本概念

    一.算法定义

    算法就是一个由有限的指令集组成的过程。从可能的输入集中给这个过程一个输入,如果系统地执行该指令集,那么对于这个特定地输入,当输出存在时,就能得到输出;当没有输出时,就什么结果也得不到。可能地输入集是指能让该算法给出能让该算法给出一个输出的所有输入。如果对于一个特定的输入就一个输出,那么就说该算法能用于这一输入,执行该算法能够得到相应的输出。

    我们要求算法对于每一个输入能停下来,这意味着每一条指令只需要有限的时间,同时每一个输入的长度是有限的,同时对于一个合法输入所对应的输出是唯一的。

    数字计算机出现后,对于可解问题研究的要求越来越多。起初人们满足于一个简单的程序能够在它需要的时间内求解一个特定的问题,而不考虑资源量。之后由于有限的可用资源和开发复杂算法的要求,提出了对尽可能少使用资源的有效算法的需求。这导致在计算领域出现了一个成为计算复杂性的新领域。

    二.时间复杂性

    在计算复杂性领域中,研究的主要目的是一个算法所需要的时间和空间,即当给合法输入时,为了得到输出,该算法所需要的时间和空间。在分析算法运行时间,通常将该算法和解决同一问题甚至不同问题的算法相比较,这样估计时间是相对的而不是绝对的;其次,无论科技如何进步,对算法运行时间的测度始终成立;最后,不是主要关心小规模输入量的情况,最关心的是在最大输入的实例时,算法的运行情况。

    1.元计算

    对任何计算步骤,他的代价总是以一个时间常量为上界,而不管输入数据或执行的算法,我们称该计算步骤为“元计算”。例如取两个整数相加的运算,不管使用何种算法,我们规定它的运算对象的大小时固定的,这一运算时间是常数。

    2.O符号

    f(n)g(n)是从自然数集到非负实数集的两个函数,如果存在一个自然数n_0和一个常数c>0使得\forall n\geq{n_0},f(n) \leq cg(n),则称f(n)O(g(n))。因此如果\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}存在,那么\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}\neq \infty蕴含着f(n)=O(g(n))。(希望找到最低上界,只考虑最高项,不考虑低阶项和非1的系数)。

    O符号也可作为一个简化工具用在等式中。例f(n)=5n^3+7n^2-2n+13\rightarrow f(n)=5n^3+O(n^2)

    3.\large \textbf{\Omiga}\large $\pmb{\Omega }$\large $\textbf{\Omega }$符号

    f(n)g(n)是从自然数集到非负实数集的两个函数,如果存在一个自然数n_0和一个常数c>0使得\forall n\geq{n_0},f(n) \geq cg(n),则称f(n)\Omega (g(n))。因此如果\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}存在,那么\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}\neq 0蕴含着f(n)=\Omega (g(n))。(希望找到最高下界)

    f(n)=\Omega (g(n)),则g(n)=O(f(n))

    4.\large \Theta符号

    f(n)g(n)是从自然数集到非负实数集的两个函数,如果存在一个自然数n_0和两个正常数,使得\forall n\geq{n_0},c_1g(n) \leq f(n) \leq c_2g(n),则称f(n)\Theta (g(n))。因此如果\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}存在,那么\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}= c蕴含着f(n)=\Theta (g(n)),其中c必须是一个大于0的常数。

    这一符号是用来表示算法的精确阶的,它蕴涵着在算法的运行时间上有确切界限。

    推论:f(n)=\Theta (g(n)),当且仅当f(n)=O(g(n))f(n)=\Omega (g(n))

    任意常函数是O(1),\Omega(1),\Theta(1)

    如,f(n)=5n^2-10n+55,则f(n)=\Theta (n^2)f(n)=logn^k,则f(n)=\Theta (logn)

    f(n)f(n+1)的关系取决于具体的f(n)是什么。当f(n)=2^n,f(n+1)=2^{n+1}=2f(n)=\Theta(f(n));而当f(n)=n!,f(n+1)=(n+1)!,f(n)=O(f(n+1))\neq \Omega(f(n+1))

    logn!=\sum_{j=1}^{n}logj=\Theta(nlogn)\sum_{j=1}^{n}\frac{n}{j}=\Theta(nlogn)

     5.o符号

    f(n)g(n)是从自然数集到非负实数集的两个函数,如果存在一个自然数n_0和对每一个一个常数c>0使得\forall n\geq{n_0},f(n) \textless cg(n),则称f(n)o(g(n))。因此如果\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}存在,那么\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}=0蕴含着f(n)=o(g(n))

    f(n)=o(g(n)),当且仅当f(n)=O(g(n)),g(n)\neq O(f(n));例如nlogn是o(n^2)的等价于nlogn是O(g(n)),但n^2不是O(nlogn)的。

    1\prec loglogn\prec logn\prec \sqrt{n}\prec n^\frac{3}{4}\prec n\prec nlogn\prec n^2\prec 2^n\prec n!\prec 2^{n^2}

     三.空间复杂性

    为了求解问题的实例而执行的计算步骤所需要的内存空间数目,它不包括分配用来存储输入的空间,换句话说,仅仅是算法需要的工作空间。算法的空间复杂性不可能超过运行时间的复杂性,因为写入每一个内存单元都至少需要一定的时间,如果用T(n)和S(n)分别代表算法的时间复杂性和空间复杂性,则有S(n)=O(T(n))。

    四.最优算法

    一般来说,如果可以证明任何一个求解问题\Pi的算法必定是\Omega (f(n)),那么把在O (f(n))时间内求解问题\Pi的任何算法都称为问题\Pi的最优算法。

    五.估算迭代次数

    1.计算迭代次数

    运行时间常常和while循环及类似结构的执行次数成正比。这样,计算迭代次数将很好得表明算法得运行时间。这种情况适用于很多算法,包括搜索、排序、矩阵乘法等。

    2.计算基本运算得频度

    如果算法中的一个元运算具有最高频度,所有其他元运算频度均在它的频度的常数倍内,则称这个元运算为基本运算。

    3.使用递推关系

    六.最坏情况和平均情况分析

    在时间复杂性的最坏情况分析中,在所有大小为n的输入中选择代价最大的;在平均情况分析中,运行时间是指在所有大小为n的输入的平均时间。

    七.输入大小(Input Size)

    一个算法执行性能的测度通常是它的输入的大小、顺序和分布的函数,其中最重要的是输入的大小。输入的大小作为一个数量,不是输入的精确测度,它解释为从属于已设计或将要设计的算法的问题。一些常用输入大小的测度如下:

    在排序和搜索问题中,用数组或表中元素的数目作为输入大小;

    在图的算法中,输入大小通常指图中的边喝顶点的数目,或二者皆有;

    在计算几何中,算法的输入大小通常用点、顶点、边、线段或多边形等的个数来表示;

    在矩阵运算中,输入大小通常是输入矩阵的维数;

    在数论算法和密码学中,通常选择输入的比特数来表示它的长度。当一个字由固定的比特数组成时,一个数字的字数也可以选来表示输入的长度。

    评价算法优劣:1)线性时间算法;2)平方/二阶时间算法;3)对数时间算法;4)指数时间算法;

    例:

        for i=1 to n
            for j=1 to n
                c[i,j]=a[i,j]+b[i,j]
            endfor
        endfor

    将两个nxn的矩阵相加的算法要执行\large n^2次加法,看上去是平方的关系,而实际上与输入的大小(矩阵维数)关系却是线性的,即线性时间算法;

        for i=2 to sqrt(n)
            if n%i=0
                输出n为合数
        endfor
        输出n为素数

     测试素数性的蛮力算法,它的时间复杂性为O(\large \sqrt{n}),由于这是个数论问题,所以输入大小用n的二进制形式中的比特数来测度,n的二进制的比特数为k=logn,则时间复杂性可写作O(\large 2^{\frac{logn}{2}}),则算法实质上是一个指数算法。

    #Algorithm FIRST
        sum←0
        for j←1 to n
            sum←sum+A[j]
        end for
        return sum
    
    #Algorithm SECOND
        sum←0
        for j←1 to n
            sum←sum+j
        end for
        return sum
    

    第一个算法是线性时间算法,数组A的规模为输入规模,即\large \Theta(n);第二个是指数时间算法,数论问题选择输入的比特数来表示它的长度,比特数k=logn,\large \Theta(n)=\large \Theta(\large 2^{logn})。

    展开全文
  • 基本概念数据是对客观事物的描述形式和编码形式的统称,是算法和程序的处理对象和计算结构。数据元素又称数据结点,简称结点,通常一个数据结点由用来描述一个独立事务的名称、数量、特性、性质的一组相关信息。多数...

    基本概念

    数据是对客观事物的描述形式编码形式的统称,是算法和程序的处理对象计算结构

    数据元素又称数据结点,简称结点,通常一个数据结点由用来描述一个独立事务的名称、数量、特性、性质的一组相关信息。

    多数情况下,一个结点包含有多个数据项,每个数据项是结点的一个域,能够用来唯一标识结点的域称为关键字域。

    例如:在设计处理学生问题的程序时,一名学生的相关信息(姓名,学号,成绩)等构成一个数据结点,学号可以作为关键字。

    数据结构: 一个有穷的结点集合D,以及该集合中各个结点之间的关系R,组成一个数据结构,表示成 B = (D,R),此时(D,R)指的是数据的逻辑结构

    例如:D = {a,b,c,d},R = {  <a,b>,<d,c>,<c,d>,<c,e> },那么(D,R)组成一个数据结构。

    物理结构:数据结构在计算机内的存储形式称为存储结构,也称为物理结构。

    存储结点:用来存储一个数据结点,在必要的时候存储该节点与其他结点之间的关系的一组存储单元。

    基本数据结构可分为表结构、树结构、图结构和散结构。

    表结构:用来表示结点之间某种先后次序关系,一个结点只有一个前驱和一个后继,但首结点没有前驱,尾结点没有后继。如学生成绩单。(一对一)

    树结构:用来表示结点之间的层次关系、分支关系、嵌套关系,一个结点只有一个前驱(根节点除外),但可以有多个后期。如某部门的组织机构。(一对多)

    图结构:用来表示结点之间最一般的关系,任何两个结点之间都可能有关系。城市交通图。(多对多)

    散结构:如果集合中任何两个结点都没有关系,或者说存在一种特殊的关系–无关关系。

    抽象数据类型:简称ADT,是将“数据”连同对其的“处理操作”封装在一起而形成的的复合体。ADT是对一个确定的数学模型以及定义在该模型上的一组操作的抽象表示,不涉及具体实现。(类比面向对象的概念)

    算法: 有穷规则的集合,而规则规定了解决某一特定问题的运算序列。

    • 有穷性:必须在执行有穷步后终止。
    • 确定性:每一步必须具有确定的定义,不能含糊不清,不带二义性。
    • 可行性:所有运算都可以精确地实现。
    • 输出数据:必须有输出数据,包括输出某种动作或控制信号。
    • 输入数据:作为执行前的初始量。不是必须。

    算法有两种表现形式:描述形式和程序形式。

    程序形式是算法的最终形式,描述形式是算法的原始形式。

    算法的描述和评价

    常用的描述语言主要有自然语言、流程图、类程序设计语言。

    对算法的评价称为算法分析,也称为评估或评测。

    算法主要评估一下两点:

    • 算法的正确性。
    • 算法的有效性。

    算法的正确性:一个正确的算法应当对所有输入数据都能给出正确的结果。算法的正确性通常要用数学归纳法去证明。

    算法的有效性:指算法的运行效率,也就算法投入运行时,将耗用多少时间,占用多少存储空间。

    算法对时间的需求称为算法的时间复杂性或时间复杂度。

    算法对空间的需求称为空间复杂性或空间复杂度。

    一般来说,一个算法的时间耗用量将随输入数据量n的增大而增大,所以时间复杂性是输入数据量n的函数,记为T(n),一般情况下要精确计算出T(n)是非常困难的,只能大体上粗略的估算。最常用的方法是求出T(n)随输入数据n增长而变化的趋势,也就是当n趋近于无穷大时,T(n)的极限情况,这种情况称为算法的渐近时间复杂性

    最坏情况和平均情况:

    最坏情况是指,对于具有相同输入的数据量的不同输入数据,算法时间用量的最大值。

    平均情况是指对于所有相同输入数据量的不同输入数据,算法耗用时间的平均値。

    计算时间复杂的的方法:

    • 支配性语句度量法:在一段程序中,往往有一条语句执行次数最多,话费时间也就是最多,其他语句执行次数的和将不超过这套语句执行次数的常数倍,那么就称这条语句在话费时间上是起支配性作用的典型语句,于是可选这条语句的执行次数作为度量这段程序花费时间的阶。
    
    某段程序形式如下:
    
        语句1;
        语句2....
        语句s;
        ....
        语句m
    
    分析:如果语句s执行了f(n)次,而除语句s外,其他语句执行次数总和不超过cf(n)次,c是常量,于是这段代码程序共执行:
    
            f(n)+cf(n) = (c+1)f(n)
    
    条基本语句,根据渐近复杂性定义,这段程序的时间复杂性为O(f(n))。
    
    
    • 分段计算法:一个复杂的程序,往往可按结构划分成相对独立的若干段,可以分别计算时间耗费,然后相加,作为整个算法的时间复杂性。
    1:若其中一段时间耗费为O(f(n)),另另一端时间耗费为O(g(m)),那么两段共耗费
    
        O(f(n)) + O(g(m)) = O(f(n)+g(m))
    
    如果m和n不是互相独立的参数,将他们相加后再简化,相加后取高阶保留
    
        O(n2) + O(n) = O(n2)
        O(n) + O(n) = O(n)
    
    
    • 分层计算法:若一段程序出现多重循环,或循环体中调用了函数,而被调函数中又带有循环,即还有多个层次,可以分别计算各层时间耗费,然后相乘,其乘积作为该段程序的时间复杂性。
    • 递推式方法:根据递推方程式计算。
    • 数学模型法:暂无。
    展开全文
  • 数据结构 第2讲 算法复杂

    千次阅读 2017-09-11 09:12:29
    该内容来源于本人著作《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825如果说数学是皇冠上的一颗明珠,那么算法就是这颗明珠上的光芒,算法让这颗明珠更加熠熠生辉,为科技进步和社会发展照亮了...

    该内容来源于本人著作《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

    如果说数学是皇冠上的一颗明珠,那么算法就是这颗明珠上的光芒,算法让这颗明珠更加熠熠生辉,为科技进步和社会发展照亮了前进的路。数学是美学,算法是艺术。走进算法的人,才能体会它的魅力。

    多年来,我有一个梦想,希望每一位提到算法的人,不再立即紧皱眉头,脑海闪现枯燥的公式、冗长的代码;希望每一位阅读和使用算法的人,体会到算法之美,像躺在法国普罗旺斯小镇的长椅上,呷一口红酒,闭上眼睛,体会舌尖上的美味,感受鼻腔中满溢的薰衣草的芳香……


    1.1 打开算法之门

    瑞士著名的科学家N.Wirth教授曾提出:数据结构+算法=程序

    数据结构是程序的骨架,算法是程序的灵魂。

    在我们的生活中,算法无处不在。我们每天早上起来,刷牙、洗脸、吃早餐,都在算着时间,以免上班或上课迟到;去超市购物,在资金有限的情况下,考虑先买什么、后买什么,算算是否超额;在家中做饭,用什么食材、调料,做法、步骤,还要品尝一下咸淡,看看是否做熟。所以,不要说你不懂算法,其实你每天都在用!

    但是对计算机专业算法,很多人都有困惑:“I can understand, but I can’tuse!”,我能看懂,但不会用!就像参观莫高窟的壁画,看到它、感受它,却无法走进。我们正需要一把打开算法之门的钥匙,就如陶渊明《桃花源记》中的“初极狭,才通人。复行数十步,豁然开朗。”

    1.2 妙不可言——算法复杂性

    我们首先看一道某跨国公司的招聘试题。

    写一个算法,求下面序列之和:

    −1,1,−1,1,…,(−1)n

    当你看到这个题目时,你会怎么想?for语句?while循环?

    先看算法1-1:

    //算法1-1 
    sum=0;
    for(i=1; i<=n; i++)
    {
      sum=sum+(-1)^n;
    }

    这段代码可以实现求和运算,但是为什么不这样算?!


    再看算法1-2:

    //算法1-2
    if(n%2==0)  //判断n是不是偶数,%表示求余数
      sum =0;
    else
      sum=-1;

    有的人看到这个代码后恍然大悟,原来可以这样啊?这不就是数学家高斯使用的算法吗?


    一共50对数,每对之和均为101,那么总和为:

    (1+100)×50=5050

    1787年,10岁的高斯用了很短的时间算出了结果,而其他孩子却要算很长时间。

    可以看出,算法1-1需要运行n+1次,如果n=100 00,就要运行100 01次,而算法1-2仅仅需要运行1次!是不是有很大差别?

    高斯的方法我也知道,但遇到类似的题还是……我用的笨办法也是算法吗?

    答:是算法。

    算法是指对特定问题求解步骤的一种描述。

    算法只是对问题求解方法的一种描述,它不依赖于任何一种语言,既可以用自然语言、程序设计语言(C、C++、Java、Python等)描述,也可以用流程图、框图来表示。一般为了更清楚地说明算法的本质,我们去除了计算机语言的语法规则和细节,采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间,它更符合人们的表达方式,容易理解,但不是严格的程序设计语言,如果要上机调试,需要转换成标准的计算机程序设计语言才能运行。

    算法具有以下特性。

    (1)有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。

    (2)确定性:每条语句有确定的含义,无歧义。

    (3)可行性:算法在当前环境条件下可以通过有限次运算实现。

    (4)输入输出:有零个或多个输入,一个或多个输出。

    算法1-2的确算得挺快的,但如何知道我写的算法好不好呢?

    “好”算法的标准如下。

    (1)正确性:正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期的需求。

    (2)易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。

    (3)健壮性:算法对非法数据及操作有较好的反应和处理。例如,在学生信息管理系统中登记学生年龄时,若将21岁误输入为210岁,系统应该提示出错。

    (4)高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次,因此不能用秒来具体计算算法消耗的时间,由于相同配置的计算机进行一次基本运算的时间是一定的,我们可以用算法基本运算的执行次数来衡量算法的效率。因此,将算法基本运算的执行次数作为时间复杂度的衡量标准。

    (5)低存储性:低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备,算法如果占用空间过大,则无法运行。算法占用的空间大小称为空间复杂度

    除了(1)~(3)中的基本标准外,我们对好的算法的评判标准就是高效率低存储

    (1)~(3)中的标准都好办,但时间复杂度怎么算呢?

    时间复杂度:算法运行需要的时间,一般将算法的执行次数作为时间复杂度的度量标准。

    看算法1-3,并分析算法的时间复杂度。

    //算法1-3 
    sum=0;                     //运行1次
    total=0;                   //运行1次
    for(i=1; i<=n; i++)        //运行n次
    {
      sum=sum+i;               //运行n次
      for(j=1; j<=n; j++)      //运行n*n次
        total=total+i*j;       //运行n*n次
    }

    把算法的所有语句的运行次数加起来:1+1+n+n+n×n+n×n,可以用一个函数T(n)表达:

    T(n)=2n2+2n+2

    n足够大时,例如n=105时,T(n)=2×1010+2×105+2,我们可以看到算法运行时间主要取决于第一项,后面的甚至可以忽略不计。

    用极限表示为:

    ,C为不等于0的常数

    如果用时间复杂度的渐近上界表示,如图1-1所示。

    从图1-1中可以看出,当n\geqslantn0,T(n)\leqslantC(n),当n足够大时,T(n)和(n)近似相等。因此,我们用О((n))来表示时间复杂度渐近上界,通常用这种表示法衡量算法时间复杂度。算法1-3的时间复杂度渐近上界为О((n))=О(n2),用极限表示为:


    图1-1 渐近时间复杂度上界

    还有渐近下界符号Ω(T(n)\geqslantC(n)),如图1-2所示。


    图1-2 渐近时间复杂度下界

    从图1-2可以看出,当n\geqslantn0,T(n)\geqslantC(n),当n足够大时,T(n)和(n)近似相等,因此,我们用Ω((n))来表示时间复杂度渐近下界。

    渐近精确界符号Θ(C1(n)\leqslantT(n)\leqslantC2(n)),如图1-3所示。

    从图1-3中可以看出,当n\geqslantn0,C1(n)\leqslantT(n)\leqslantC2(n),当n足够大时,T(n)和(n)近似相等。这种两边逼近的方式,更加精确近似,因此,用Θ ((n))来表示时间复杂度渐近精确界。


    图1-3 渐进时间复杂度精确界

    我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。

    看算法1-4,并分析算法的时间复杂度。

    //算法1-4
    i=1;              //运行1次
    while(i<=n)     //可假设运行x次
    {
      i=i*2;         //可假设运行x次
    }

    观察算法1-4,无法立即确定while 及i=i*2运行了多少次。这时可假设运行了x次,每次运算后i值为2,22,23,…,2x,当i=n时结束,即2xn时结束,则x=log2n,那么算法1-4的运算次数为1+2log2n,时间复杂度渐近上界为О((n))=О(log2n)。

    在算法分析中,渐近复杂度是对算法运行次数的粗略估计,大致反映问题规模增长趋势,而不必精确计算算法的运行时间。在计算渐近时间复杂度时,可以只考虑对算法运行时间贡献大的语句,而忽略那些运算次数少的语句,循环语句中处在循环内层的语句往往运行次数最多,即为对运行时间贡献最大的语句。例如在算法1-3中,total=total+i*j是对算法贡献最大的语句,只计算该语句的运行次数即可。

    注意:不是每个算法都能直接计算运行次数。

    例如算法1-5,在a[n]数组中顺序查找x,返回其下标i,如果没找到,则返回−1。

    //算法1-5 
    findx(int x)      //在a[n]数组中顺序查找x
    { 
    for(i=0; i<n; i++)  
    {
       if (a[i]==x)  
         return i;    //返回其下标i
       
      return -1;
    }

    我们很难计算算法1-5中的程序到底执行了多少次,因为运行次数依赖于x在数组中的位置,如果第一个元素就是x,则执行1次(最好情况);如果最后一个元素是x,则执行n次(最坏情况);如果分布概率均等,则平均执行次数为(n+1)/2。

    有些算法,如排序、查找、插入等算法,可以分为最好最坏平均情况分别求算法渐近复杂度,但我们考查一个算法通常考查最坏的情况,而不是考查最好的情况,最坏情况对衡量算法的好坏具有实际的意义

    我明白了,那空间复杂度应该就是算法占了多大存储空间了?

    空间复杂度:算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。

    空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括:

    (1)输入/输出数据;

    (2)算法本身;

    (3)额外需要的辅助空间。

    输入/输出数据占用的空间是必需的,算法本身占用的空间可以通过精简算法来缩减,但这个压缩的量是很小的,可以忽略不计。而在运行时使用的辅助变量所占用的空间,即辅助空间是衡量空间复杂度的关键因素。

    看算法1-6,将两个数交换,并分析其空间复杂度。

    //算法1-6 
    swap(int x,int y)  //x与y交换 
    { 
      int temp;
      temp=x;  //temp为辅助空间 ①
      x=y;   
      y=temp; 
    }

    两数的交换过程如图1-4所示。


    图1-4 两数交换过程

    图1-4中的步骤标号与算法1-6中的语句标号一一对应,该算法使用了一个辅助空间temp,空间复杂度为О(1)。

    注意:递归算法中,每一次递推需要一个栈空间来保存调用记录,因此,空间复杂度需要计算递归栈的辅助空间。

    看算法1-7,计算n的阶乘,并分析其空间复杂度。

    //算法1-7 
    fac(int n)  //计算n的阶乘
    {  
      if(n<0)   //小于零的数无阶乘值
      {  
         printf("n<0,data error!"); 
         return -1;
      }
      else if(n= =0 || n= =1) 
               return 1; 
             else 
               return n*fac(n-1); 
    }

    阶乘是典型的递归调用问题,递归包括递推和回归。递推是将原问题不断分解成子问题,直到达到结束条件,返回最近子问题的解;然后逆向逐一回归,最终到达递推开始的原问题,返回原问题的解。

    思考:试求5的阶乘,程序将怎样计算呢?

    5的阶乘的递推和回归过程如图1-5和图1-6所示。


    图1-5 5的阶乘递推过程


    图1-6 5的阶乘回归过程

    图1-5和图1-6的递推、回归过程是我们从逻辑思维上推理,用图的方式形象地表达出来的,但计算机内部是怎样处理的呢?计算机使用一种称为“栈”的数据结构,它类似于一个放一摞盘子的容器,每次从顶端放进去一个,拿出来的时候只能从顶端拿一个,不允许从中间插入或抽取,因此称为“后进先出”(last in first out)。

    5的阶乘进栈过程如图1-7所示。


    图1-7 5的阶乘进栈过程

    5的阶乘出栈过程如图1-8所示。


    图1-8 5的阶乘出栈过程

    从图1-7和图1-8的进栈、出栈过程中,我们可以很清晰地看到,首先把子问题一步步地压进栈,直到得到返回值,再一步步地出栈,最终得到递归结果。在运算过程中,使用了n个栈空间作为辅助空间,因此阶乘递归算法的空间复杂度为О(n)。在算法1-7中,时间复杂度也为О(n),因为n的阶乘仅比n−1的阶乘多了一次乘法运算,fac(n)=n*fac(n−1)。如果用T(n)表示fac(n)的时间复杂度,可表示为:

                    T(n)= T(n−1)+1

                      = T(n−2)+1+1

                      ……

                      = T(1)+…+1+1

                      =n

    1.3 美不胜收——魔鬼序列

    趣味故事1-1:一棋盘的麦子

    有一个古老的传说,有一位国王的女儿不幸落水,水中有很多鳄鱼,国王情急之下下令:“谁能把公主救上来,就把女儿嫁给他。”很多人纷纷退让,一个勇敢的小伙子挺身而出,冒着生命危险把公主救了上来,国王一看是个穷小子,想要反悔,说:“除了女儿,你要什么都可以。”小伙子说:“好吧,我只要一棋盘的麦子。您在第1个格子里放1粒麦子,在第2个格子里放2粒,在第3个格子里放4粒,在第4个格子里放8粒,以此类推,每一格子里的麦子粒数都是前一格的两倍。把这64个格子都放好了就行,我就要这么多。”国王听后哈哈大笑,觉得小伙子的要求很容易满足,满口答应。结果发现,把全国的麦子都拿来,也填不完这64格……国王无奈,只好把女儿嫁给了这个小伙子。

    解析

    棋盘上的64个格子究竟要放多少粒麦子?

    把每一个放的麦子数加起来,总和为S,则:

    S=1+21+22+23+…+263   ①

    我们把式①等号两边都乘以2,等式仍然成立:

    2S=21+22+23+…+263+264   ②

    式 ②减去式①,则:

    S=264−1 =18 446 744 073 709 551 615

    据专家统计,每个麦粒的平均重量约41.9毫克,那么这些麦粒的总重量是:

       18 446 744 073 709 551 615×41.9=772 918 576 688 430 212 668.5(毫克)

                       ≈7729(亿吨)

    全世界人口按60亿计算,每人可以分得128吨!

    我们称这样的函数为爆炸增量函数,想一想,如果算法时间复杂度是О(2n) 会怎样?随着n的增长,这个算法会不会“爆掉”?经常见到有些算法调试没问题,运行一段也没问题,但关键的时候宕机(shutdown)。例如,在线考试系统,50个人考试没问题,100人考试也没问题,如果全校1万人考试就可能出现宕机。

    注意:宕机就是死机,指电脑不能正常工作了,包括一切原因导致的死机。计算机主机出现意外故障而死机,一些服务器(如数据库)死锁,服务器的某些服务停止运行都可以称为宕机。

    常见的算法时间复杂度有以下几类。

    (1)常数阶。

    常数阶算法运行的次数是一个常数,如5、20、100。常数阶算法时间复杂度通常用О(1)表示,例如算法1-6,它的运行次数为4,就是常数阶,用О(1)表示。

    (2)多项式阶。

    很多算法时间复杂度是多项式,通常用О(n)、О(n2)、О(n3)等表示。例如算法1-3就是多项式阶。

    (3)指数阶。

    指数阶时间复杂度运行效率极差,程序员往往像躲“恶魔”一样避开它。常见的有О(2n)、О(n!)、О(nn)等。使用这样的算法要慎重,例如趣味故事1-1。

    (4)对数阶。

    对数阶时间复杂度运行效率较高,常见的有О(logn)、О(nlogn)等,例如算法1-4。

    常见时间复杂度函数曲线如图1-9所示。


    图1-9 常见函数增量曲线

    从图1-9中可以看出,指数阶增量随着x的增加而急剧增加,而对数阶增加缓慢。它们之间的关系为:

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

    我们在设计算法时要注意算法复杂度增量的问题,尽量避免爆炸级增量。

    展开全文
  • 算法复杂网络

    千次阅读 2019-09-26 11:46:12
    笔者最近一直在研究图算法,在研究图算法前,对复杂网络分析进行了研究,笔者的上篇博文就是对研究的复杂网络分析的内容进行的总结。图算法,字面意思上看,就是对图进行处理的算法。在学习前,笔者一直有个疑问,图...

    笔者最近一直在研究图算法,在研究图算法前,对复杂网络分析进行了研究,笔者的上篇博文就是对研究的复杂网络分析的内容进行的总结。图算法,字面意思上看,就是对图进行处理的算法。在学习前,笔者一直有个疑问,图究竟属不属于复杂网络?再学习了如下两本书中的内容后,笔者还是没有得到准确的答案。

    注:本书部分内容及观点总结自以下书籍:
    1.《Graph Algorithms》Mark Needham, Amy E.Hodler著,2019年5月版;
    2.《Spark GraphX》Micheal S.Malak, Robin East著,2017年4月版;
    3.《复杂网络算法与应用》孙玺菁,司守奎 著,2015年6月版。

    在图算范与复杂网络分析的书中,笔者学习到了很多内容相似甚至相同的处理算法,如中心性计算,路经查询等,包括复杂点的社团结构。那么,二者之间到底是什么关系?笔者个人认为,重要的事情说n遍,仅限作者个人意见,…,仅限作者个人意见,笔者认为图算法应该属于复杂网络分析中的一种特殊情况,而复杂网络分析并不是仅有图算法内容。

    下面笔者简单对基本图算法进行总结:
    1路径寻找
    路径寻找算法建立在图寻找算法之上,为了寻找两个节点间的最优路径。路径寻找算法包括最短路径、到所有点最短路径和单资源最短路径、最小生成树、随机游走。
    1.1最短路径
    加权最短路径
    输入:起始节点、终止节点
    输出:最短路径长度
    遍历方法:
    1)广度优先寻找:先遍历节点直接相连的节点,遍历完成后再遍历相邻节点直接相连的节点,以此类推。
    2)深度优先寻找:首先遍历节点相连的点,当遍历到该节点时,若该节点有其他相连节点,则继续遍历相邻节点,不需要折返。

    1.2全节点对最短路径
    1.2.1到所有点最短路径
    输入:起始节点
    输出:从起始节点到图其他节点的最短路径
    算法步骤:
    1)设定节点到本节点的距离为无穷大;计算并记录从起始节点经一跳可到达的节点及其路径权值;
    2)计算从起始节点经两跳可到达的节点及其路径权值和,与步骤1)中结果对比,若相同起始节点,路径权值和小于步骤1)中的,则更新权值路径;
    3)重复步骤2),可得出最终起始节点到全图各节点的最短路径。

    1.2.2单资源最短路径
    输入:起始节点
    输出:从起始节点到其他各节点的最短路径
    算法步骤:
    1)从起始节点开始,首先选择路径权值最小的边连接的节点;
    2)再从起始节点开始计算,选择到达路径权值最小的节点;
    3)不断重复步骤2),直到遍历完所有节点。

    1.3最小生成树
    输入:起始节点
    输出:由起始节点构建的最小生成树
    算法步骤:
    1)从起始节点开始,选择边权值最小的点,将被选中的节点添加到树中;
    2)重复选择边权值最小的点,当没有新的节点被添加入生成树的时候,算法介数。
    注:单资源算法和最小生成树算法的区别:单资源算法每次计算的是从根节点开始路径权值的总和,而最小生成树仅仅看下一步的权值。

    2中心性计算
    2.1度中心性
    节点的出边个数称为出度,入边个数称为入度。
    2.2紧密中心性
    紧密中心性标准化方程:
    在这里插入图片描述
    其中,u为节点,n为图中节点的个数,d(u,v)为节点v与节点u之间的最短距离。为了解决无连接图的干扰,引入调和中心性,其标准方程如下:
    在这里插入图片描述
    2.3介数中心性
    介数中心性计算公式如下:
    在这里插入图片描述
    其中,u为节点,p为节点s与节点t之间最短路径的个数,p(u)为节点s与节点t之间经过节点u的最短路径的个数。

    2.4 PageRank
    PageRank计算公式如下所示:
    在这里插入图片描述
    其中,我们假设u页有从T1页到Tn页的引文;d是取值为0至1之间的抑制参数,常设置为0.85;1-d表示不遵循任何关系直接到达节点的可能性;C(Tn)表示节点T的出度。

    3社团检测算法
    3.1三角计数和聚类系数用于分析总体关系密度
    测量节点产生三角计数和度的多少,为了决定哪些节点倾向于聚集在一起。
    节点u的聚类系数计算公式如下:
    在这里插入图片描述
    其中,u表示节点;R(u)表示通过u的三角计数;k(u)表示节点u的度。
    聚类系数能够使我们快速的找到明显的小团体。

    3.2强连通组件和连通组件用于找到连接的群集
    强连通组件:查找可以从同一组中的每个其他节点按照关系的方向访问每个节点的组;
    连通组件:查找可以从同一组中的每个其他节点访问每个节点的组,而不考虑关系的方向。

    3.3标签传递为了根据节点标签快速推断团体
    根据多数相邻节点,以标签传递的方式推断团体,是一个快速寻找社团的方法。
    标签传递算法:
    输入:带标签的节点
    输出:不同标签种类的社团
    算法步骤:
    1)首先确定带有标签的节点;
    2)将与标签节点直接相连的节点打上其对应的标签;
    3)最近标记的节点被激活,变为新的标签节点,重复步骤2);
    4)当遇到两不同标签节点都准备激活同一节点时,可根据设定关系(如根据边权值的大小)进行决定选择;
    5)标签传递结束。
    注:标签传递算法每次运行的结果都可能不一样,因为初始节点的选择可能不同。

    3.4 Louvain模块化为了查看团体质量和层次结构
    通过将关系权重和密度与定义的估计值或平均值进行比较,使团体的设定精确度最大化。
    一个团体的模块系数计算公式如下:
    在这里插入图片描述
    其中,L表示全团体的关系数量;Lc表示分隔中的关系的数量;kc表示分隔中所有节点的度值和。模块度的计算公式如下:
    在这里插入图片描述
    其中,u和v表示节点;m表示总的关系权重;Auv是节点u和v之间关系的权值;ku、kv分别是节点u和v关系权重的总和;最后类似激活函数一样的式子表示节点u、v是否在同一社团,若在同一社团,则其值为1,若不在,则为0。

    Louvain模块化算法:
    输入:节点个数及节点间的权值,及节点是否在同一社团
    输出:最优化的子图模块
    算法步骤:
    1)将图中的每个节点看成一个独立的社区,社区的数目与节点个数相同;
    2)对每个节点u,依次尝试把节点u分配到其每个邻居节点所在的社区,计算分配前与分配后的模块度变化Delta Q,并记录Delta Q最大的那个邻居节点,如果maxDelta Q>0,则把节点u分配Delta Q最大的那个邻居节点所在的社区,否则保持不变;
    3)重复2),直到所有节点的所属社区不再变化;
    4)对图进行压缩,将所有在同一个社区的节点压缩成一个新节点,社区内节点之间的边的权重转化为新节点的环的权重,社区间的边权重转化为新节点间的边权重;
    5)重复1)直到整个图的模块度不再发生变化。

    注:常见图算法工具NetworkX包,Spark GraphX,Neo4j等。

    展开全文
  • 数据结构算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...
  • 主要是研究非数值性程序设计中计算机操作的... 算法(Algorithm)是一个有穷规则(或语句、指令)的有序集合。它确定了解决某一问题的一个运算序列。对于问题的初始输入,通过算法有限步的运行,产生一个或多个输出。
  • 算法之美——算法复杂

    千次阅读 2017-08-17 13:41:22
    第1章 算法之美《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825如果说数学是皇冠上的一颗明珠,那么算法就是这颗明珠上的光芒,算法让这颗明珠更加熠熠生辉,为科技进步和社会发展照亮了前进的...
  • 算法基本逻辑结构-概述

    千次阅读 2013-11-30 22:49:57
     引用百度百科的算法定义:算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤,或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。  我们可以用自然语言来...
  • 数据结构基本算法(python版) day 1 数据结构算法 都是计算机程序的基本构建模块,算法描述了最终能解决一个问题的计算过程,而数据结构呢。。。我个人的理解是构成一段或庞大,或复杂的,或相互关联,或毫无...
  • 算法入门之基本数据结构:链表

    万次阅读 2020-05-16 20:30:19
    前面我们简单的对队列和栈有了个了解,今天我们还要将一种数据结构,Java中很多集合类都是由这几种数据结构演变而来的,除了队列和栈还有我们今天要说的链表,链表其实还是蛮复杂的,在C中有个指针用来实现,很多人...
  • 算法基本控制结构_三大结构

    千次阅读 2019-11-25 21:11:27
    ok,前面已经复习了不少的东西了,现在开始正式敲门了,...计算机和人不同,人脑有一套完整的逻辑思维和轻重缓急的辨别“器件”,他们通过各种各样的或简单或复杂的操作,让你对所进行的工作有一定的判断,进而持...
  • 算法基本概念

    千次阅读 2016-11-22 23:57:01
    算法基本概念,以及流程图的认识和基本画法........
  • 考研数据结构笔记--数据结构算法基本概念数据结构基本概念算法基本概念 数据结构基本概念 数据 数据是对客观事物的符合表示,在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符合的总称...
  • 前端基本的数据结构算法了解

    千次阅读 2018-11-06 17:56:36
    提到数据结构算法都感觉这应该是后端要掌握的知识,对前端来说只要写写页面,绑定事件,向后台发发数据就好了,用不到数据结构算法,也许对于一些数据查找 简单的for循环就能搞定,也许只是提高了几毫米而已,可...
  • 算法复杂性分析概述

    千次阅读 2019-04-25 18:03:56
    写在前面 算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)=T(n,i);...因此作为编程人员掌握基本算法时间复杂度分析方法很有必要的。 算法的空间复杂度与时间复杂度计量方法相似且相对...
  • 【版权申明】未经博主同意,不允许转载!(请尊重原创,博主保留追究权) ... 出自【zejian的博客】 关联文章:java数据结构算法之顺序表与链表设计与实现...java数据结构算法之改良顺序表与双链表类似ArrayList和L
  • 谈谈算法基本思想

    千次阅读 2016-06-08 06:49:13
    David Berlinkshi说:有两种思想,象珠宝商放在天鹅绒上的宝石一样熠熠发光,一是微积分,另一个就是算法。如果说微积分及在其基础上建立的数学分析体系造就了现代科学,而算法则造就了现代世界。 算法是计算机科学...
  • 动态规划算法基本要素[^2]5.1 最优子结构5.2 重叠子问题6.一些经典的动态规划问题 1.序 近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法基本思想、使用动态规划算法...
  • 数据结构算法基础1.1 数据结构研究对象计算机解决问题的步骤:1.3 基本概念和术语1. 数据(data):能够输入到计算机中,并且能被计算机处理的符号的集合。2. 数据元素(data element):数据的基本单位,它在...
  • 图谱理论与复杂网络相关算法

    千次阅读 2020-05-13 20:57:36
    1.图谱问题研究背景 现实生活中的各种复杂网络都可以用图有效表示。...由于复杂网络节点规模巨大,通常很难找到特定网络拓扑结构与图谱性质间的直接相关性,求解复杂网络社团分割问题的精确解是一个NP难问题。 2
  • dictmatch基本数据结构算法 dictmatch其实是实现了最简单的Trie树的算法,而且并没有进行穿线改进,因此其是需要回朔的。但是其使用2个表来表示Trie树,并对其占用空间大的问题进行了很大的优化,特点是在建树的...
  • 数据结构算法

    千次阅读 2021-04-27 22:23:16
      数据结构主要研究非数值计算问题程序中的操作对象以及它们之间的关系,不是研究复杂算法。   数据结构中的基本概念: 数据: 程序的操作对象,用于描述客观事物。数据是能输入计算机且能被计算机.
  • 遗传算法(三)——基本遗传算法

    千次阅读 2021-01-05 21:42:53
    3.1基本遗传算法描述
  • 【大总结1】数据结构与传统算法总结

    万次阅读 多人点赞 2018-12-18 13:28:38
    由于时间和水平有限,肯定有错误或者写得不好的地方 欢迎在文章下评论指出。 涉及语言: py3:注重算法本身的知识 ...java:实现较复杂数据结构 一、概述 c语言知识体系 算法体系参考 ...
  • 算法思想——穷举 (用java语言实现 鸡兔同笼问题,韩信点兵问题等) 2. 递推 简单的动态规划,根据递推公式,累加。 经典案例: 斐波那契函数:F(n) = F(n-1)+ F(n-2),随便给一个n,问F(n)为多少。java语言...
  • 数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你...
  • 现实上的可计算——计算复杂性理论 几个例子: 关于例2,如果采用蛮力算法—穷举法,则可能的非负整数解的个数为 根据Stirling公式 可得 ( 此处还有不明白之处,...
  • Java数据结构算法(一)——开篇

    万次阅读 多人点赞 2014-09-15 07:03:40
    看的是——《Java数据结构算法》一书,作者Robert Lafore。 目录 1)数据结构算法有什么用? 2)技术与通俗 3)驱动力学习 1)数据结构算法有什么用? 当你用着java里面的容器类很爽的时候,你有没有想过,怎么...
  • python复杂网络库networkx:算法

    万次阅读 2017-01-04 16:22:54
    http://blog.csdn.net/pipisorry/article/details/54020333Networks算法Algorithms最短路径Shortest Pathsshortest_pathall_shortest_pathsshortest_path_lengthaverage_shortest_path_lengthhas_pathAdvanced ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 360,804
精华内容 144,321
关键字:

复杂算法的基本结构