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

    2018-02-20 11:24:42
    数据结构:问题的数学模型算法:处理问题的策略算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作算法必须满足五个重要特性: (1)有穷性:算法必须能在执行有穷步骤...

    数据结构:问题的数学模型

    算法:处理问题的策略

    算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作

    算法必须满足的五个重要特性: 
    (1)有穷性:算法必须能在执行有穷步骤之后结束,每一步骤都能在有限时间内完成;
    (2)确定性:算法的每一个步骤必须是确切定义的。并且,对于一种输入,算法只有一条执行路径,即对于相同的输入只能得到相同的输出;
    (3)可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现;
    (4)有输入:作为算法加工对象的量值,通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中。
    (5)有输出:它是一组与“输入”有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。

    算法效率分析:

      时间耗费:(渐进)时间复杂度


      空间耗费:(渐进)空间复杂度

    算法执行期间需要占用的存储空间由3部分组成:
    (1) 数据元素集合所占的空间
    (2) 程序本身所占的空间
    (3) 辅助变量所占的空间(辅助空间)
        其中,辅助空间需要分析和评估,用算法的空间复杂度来度量

    展开全文
  • 1.4 算法和算法分析 1.4.1 算法 算法是对特定问题求解步骤的一种描述它是指令 的有限序列其中每一条指令表示一个或多个操作一 个算法必须满足以下五个重要特性 1 有穷性 2 确定性 3 可行性 4 输入 5 输出 1 有穷性 ...
  • 算法算法分析

    2013-07-23 09:49:07
     一个算法必须满足以下五个重要特性: 1.有穷性  2.确定性 3.可行性 4.有输入  5.有输出 二:设计算法的原则   1.正确性 2.可读性 3、健壮性 4.高效率与低存储量需求 三:算法的时间...

    一:算法的基本概述

    算法是为了解决某类问题而规定的一个有限长的操作序列。  
     一个算法必须满足以下个重要特性
    1.有穷性  2.确定性   3.可行性
    4.有输入  5.有输出
    二:设计算法的原则
     
    1.正确性
    2.可读性
    3、健壮性
    4.高效率与低存储量需求
    三:算法的时间复杂度简介
      语句频度:语句重复执行的次数
      所有语句频度之和记做f(n),它是该算法所求解的问题规模n的函数;
     T(n)=O(f(n))当n->∞时,T(n)的数量级称为渐近时间复杂度,简称时间复杂度。            
      一个特定算法的“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),或者说,它是问题规模的函数。与待处理数据的初态无关。
     
     
    一个算法的时间复杂度还可以具体分为最好、最差(最坏)、平均三种情况讨论。
    最好情况下最容易求出,但没有多大实际意义
    最差情况下也容易求出,而且这是估计该算法执行时间的一个上界
    平均情况下最难计算:在很多情况下地输入数据集出现的概率难以确定。
    一般,算法的时间复杂度如无特别说明,则指最坏情况下的时间复杂度
     
     
    展开全文
  • 一个算法必须满足一下五个重要特性: 有穷性 算法的每个步骤都能在有限时间内完成 确定性 对于每种情况下所应执行的操作,在算法中都有明确的规定 可行性 算法中的所有操作都必须足够基本,都可以通过已经实现的...

    一.算法

    算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足一下五个重要特性:

    1. 有穷性            算法的每个步骤都能在有限时间内完成
    2. 确定性            对于每种情况下所应执行的操作,在算法中都有明确的规定
    3. 可行性            算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现
    4. 有输入            作为算法加工对象的量值,通常体现为算法中的一组变量
    5. 有输出            一组与"输入"有确定关系的量值,是算法进行信息加工后得到的结果

    二.算法设计的原则

    设计算法时,通常应考虑以下目标:

    1. 正确性
    2. 可读性
    3. 健壮性
    4. 高效率与低存储量需求(高效性)

    三.算法效率的衡量方法和准则

    1.通常有两种衡量算法效率的方法:

    1)事后统计法

          缺点:1.必须执行程序

                     2.其他因素掩盖算法本质

    2)事前分析估算法

    2.和算法执行时间相关的因素:

    3. 一个特定算法的"运行工作量"的大小,只依赖于问题的规模(通常用整数n表示),或者说,它时问题规模的函数。例如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记为:

                                  T(n) = O(f(n))     称T(n)为算法的(渐进)时间复杂度

    1. 算法选用的策略
    2. 问题的规模
    3. 编写程序的语言
    4. 编译程序所产生的机器代码的质量
    5. 计算机执行指令的速度

    怎么估算算法的时间复杂度?

    1)算法 = 控制结构 + 原操作(固有数据类型的操作,即计算机执行的基本操作)

    2)算法的执行时间 = ∑原操作(i)的执行次数 * 原操作(i)的执行时间

    3)算法的执行时间原操作执行次数之和成正比

    4)从算法中选取一种对于所研究的问题来说是"基本操作(对程序起决定作用的操作)"的原操作,以该原操作在算法中重复执行的次数作为算法运行时间的衡量准则

    例1.

    for(int i=1;i<=n;++i)  //n
        for(int j=1;j<=n;++j){  //n
        c[i][j] = 0;
        for(int k=1;k<=n;++k){   //n
         c[i][j] += a[i][k]*b[k][j];    //共执行n*n*n次
     }
    }

    原操作:赋值,相加,相乘

    基本操作:相乘(即乘法的执行次数可以作为算法时间复杂度的衡量标准)

    时间复杂度:T(n) = O(n^3)

    例2.

    void select_sort(int a[],int n){
        //将a中整数序列重新排列成自小到大的整数序列
        for(int i=0;i<n-1;++i){  //n-1
        int min=i;
        for(int k=i+1;k<n;++k) //n-1+n-2+n-3+...+1 = n(n-1)/2 = n^2-n/2
        if(a[k]<a[min]) min = k;
        if(min!=i){
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;  
      }
     }
    }

    控制结构:两重循环

    原操作:比较,赋值,交换

    基本操作:比较(数据元素)操作

    时间复杂度:与n^2成正比,所以为T(n) = O(n^2)

    例3.

    void bubble_sort(int a[],int n){
        //将a中整数序列重新排列成自小到大的整数序列
        for(int i=n-1,change=TRUE;i>1&&change;--i){  //最好情况只执行1次,最坏执行n-1次
            change = FALSE;
            for(int j=0;j<i;++j){    //n^2-n/2
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    change = TRUE;
                }
            }
        }
    }

    基本操作:赋值操作

    时间复杂度:一般按最坏时间复杂度,即T(n) = O(n^2)

    四.算法的存储空间需求

    算法的空间复杂度:S(n) = O(g(n))

    1)表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增持率相同

    2)算法的存储量包含:

    3)若输入 数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的辅助变量所占额外空间,若所需额外空间相对于输入数据量是常数,则称此算法为原地工作

    1. 输入数据所占空间
    2. 程序本身所占空间
    3. 辅助变量所占空间
    展开全文
  • 1、算法五个重要特性(有穷性、确定性、可行性、输入、输出) 2、算法设计的要求(正确性、可读性、健壮性、效率与低存储量需求) 3、算法与程序的关系: (1)一个程序不一定满足有穷性。例操作系统,只要整个...

    《数据结构》必须掌握的知识点与算法

    第一章 绪论

    1、算法的五个重要特性(有穷性、确定性、可行性、输入、输出)

    2、算法设计的要求(正确性、可读性、健壮性、效率与低存储量需求)

    3、算法与程序的关系:

    (1)一个程序不一定满足有穷性。例操作系统,只要整个系统不遭破坏,它将永远不会停止,即使没有作业需要处理,它仍处于动态等待中。因此,操作系统不是一个算法。

    (2)程序中的指令必须是机器可执行的,而算法中的指令则无此限制。算法代表了对问题的解,而程序则是算法在计算机上的特定的实现。

    (3)一个算法若用程序设计语言来描述,则它就是一个程序。

    4、算法的时间复杂度的表示与计算(这个比较复杂,具体看算法本身,一般关心其循环的次数与N的关系、函数递归的计算)

    第二章 线性表

    1、线性表的特点:

    (1)存在唯一的第一个元素;(这一点决定了图不是线性表)

    (2)存在唯一的最后一个元素;

    (3)除第一个元素外,其它均只有一个前驱(这一点决定了树不是线性表)

    (4)除最后一个元素外,其它均只有一个后继。

    2、线性表有两种表示:顺序表示(数组)、链式表示(链表),栈、队列都是线性表,他们都可以用数组、链表来实现。

    3、顺序表示的线性表(数组)地址计算方法:

    (1)一维数组,设DataType  a[N]的首地址为A0,每一个数据(DataType类型)占m个字节,则a[k]的地址为:Aa[k]=A0+m*k(其直接意义就是求在数据a[k]的前面有多少个元素,每个元素占m个字节)

    (2)多维数组,以三维数组为例,设DataType  a[M][N][P]的首地址为A000,每一个数据(DataType类型)占m个字节,则在元素a[i][j][k]的前面共有元素个数为:M*N*i+N*j+k,其其地址为:

    Aa[i][j][k]=A000+m*(M*N*i+N*j+k);

    4、线性表的归并排序:

    设两个线性表均已经按非递减顺序排好序,现要将两者合并为一个线性表,并仍然接非递减顺序。可见算法2.2

    5、掌握线性表的顺序表示法定义代码,各元素的含义;

    6、顺序线性表的初始化过程,可见算法2.3

    7、顺序线性表的元素的查找。

    8、顺序线性表的元素的插入算法,注意其对于当原来的存储空间满了后,追加存储空间(就是每次增加若干个空间,一般为10个)的处理过程,可见算法2.4

    9、顺序线性表的删除元素过程,可见算法2.5

    10、顺序线性表的归并算法,可见算法2.7

    11、链表的定义代码,各元素的含义,并能用图形象地表示出来,以利分析;

    12、链表中元素的查找

    13、链表的元素插入,算法与图解,可见算法2.9

    14、链表的元素的删除,算法与图解,可见算法2.10

    15、链表的创建过程,算法与图解,注意,链表有两种(向表头生长、向表尾生长,分别用在栈、队列中),但他们的区别就是在创建时就产生了,可见算法2.11

    16、链表的归并算法,可见算法2.12

    17、建议了解所谓的静态单链表(即用数组的形式来实现链表的操作),可见算法2.13

    18、循环链表的定义,意义

    19、循环链表的构造算法(其与单链表的区别是在创建时确定的)、图解

    20、循环链表的插入、删除算法、图解

    21、双向链表的定义,意义

    22、双向链表的构造算法(其与单链表的区别是在创建时确定的)、图解

    23、双向链表的插入、删除算法、图解,可见算法2.18、2.19

    24、补充:在循环链表中,只设立一个表尾指针比只设立一个表头指针更方便些,为什么?

    第三章 栈和队列

    1、栈的顺序表示与实现

    2、栈的链表表示与实现

    3、栈的入栈、出栈操作算法

    4、栈的几个经典应用(迷宫、表达式求值)

    5、栈与递归的实现,如Hanoi塔问题

    6、队列链式表示与实现

    7、链式队列的入队、出队操作算法

    8、循环队列的表示(顺序表示)和实现,特别注意其判满、判空方法、入队操作、出队操作的实现(特别重要,考得频率很大)

    9、补充:共享栈的方法与实现(即两个栈共享一个空间,他们采用栈顶相向,迎面增长的存储方式)

    10、补充:用两个栈来模拟一个队列的思路、算法

    11、补充:表达式(前缀、后缀、中缀)的表达互换,这个操作要求对栈在表达式求值中的应用相当熟练,并要求对后面的二叉树相当熟练

    12、补充:了解双端队列(只需了解)

    13、补充:链栈比顺序栈的优点与缺点

    14、补充:一系列元素依次入栈再出栈的顺序,经典题目为:有5个元素,其入栈次序为A、B、C、D、E,以下哪种出栈的顺序是不可能的?

    15、补充:了解用循环链表实现队列,注意在该循环链表中只有一个头指针或一个表尾指针(只需了解)

    16、补充:根据给出的数学公式,写出对应的递归算法,最经典的就是用递归求阶乘。

    第六章 树和二叉树

    1、几个重要的概念:树、森林、子树、根、终端结点(叶子)、非终端结点、双亲、孩子、兄弟、堂兄弟、度、深度、有序树、无序树、二叉树、k叉树、完全二叉树、满二叉树、线索二叉树;

    2、二叉树的5种基本形态;

    3、二叉树的5个重要性质:

    (1)在二叉树的第i层上至多有2i-1个结点(i≥1);

    (2)深度为k的二叉树至多有2k-1个结点,(k≥1)

    (3)对任何一棵二叉树T,如果其终端结点(叶子)数为n0,度为2的结点数为n2,则n0=n2+1;

    (4)具有n个结点的完全二叉树的深度为;

    (5)如果对一棵有n个结点的完全二叉树(其深度为)的结点按性层序编号(从第1层到第层,每层从左到右),则对任一结点i(1≤i≤n),有:

    (i)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲Parent(i)是结点

    (ii)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LChild(i)是结点2i;

    (iii)如果2i+1>n,则结点i无右孩子;否则其右孩子RChild(i)是结点2i+1

    利用完全二叉树的上述性质,能处理大多数完全二叉树的计算题;

    4、二叉树的存储结构:

    (1)了解顺序存储结构,只做了解;

    (2)链式存储结构,重要,需要掌握,后面的算法都是基于此结构;

    5、二叉树的遍历:

    (1)能对任意一棵二叉树进行手动前序、中序、后序遍历;

    (2)能将由前序+中序、后序+中序给出的序列还原成一棵二叉树;

    (3)能将一个数学表达式用中序方法将其用二叉树画出来,并能写出其前缀(波兰式)、中缀、后缀(逆波兰式)表达出来;

    6、二叉树的遍历递归算法(注意前、中、后序三个算法只有细微的差别),可见算法6.1,而他们的非递归算法不作要求;

    7、建立二叉树链表的递归算法,可见算法6.4;

    8、线索二叉树的存储结构图;

    9、能用手画出任意二叉树对应的线索二叉树(中序、后序线索);

    10、线索二叉树的非递归遍历算法,可见算法6.5;

    11、理解线索二叉树的中序线索化过程算法,可见算法6.6;

    12、手动写出任意森林、树的深度优先、广度优先遍历顺序;

    13、森林、二叉树的转换过程,能用手画出即可;

    14、哈夫曼树的相关概念:路径长度、带权路径长度WPL、权值;

    15、二叉哈夫曼树的构造过程,能用手动构造,并能将构造好的树用编码表示出来;

    16、了解哈夫曼树的构造算法,可见算法6.12,只需要了解,无需掌握;

    17、记住树的记数公式:对一棵有n个结点的有棵不同的二叉树

    18、补充:二叉排序树、插入、删除结点的操作(在查找一章中有详述);

    19、补充:满二叉树、完全二叉树用数组存储方式,其元素、结点对应关系;

    20、补充:求二叉树的高度(深度)算法;

    21、补充:将二叉树中左、右孩子交换的算法;

    22、补充:将用数组存储的完全二叉树转换成链式结构的算法;

    23、补充:对用数组存储的完全二叉树进行非递归的前序、中序、后序遍历算法;

    24、补充:求二叉树中叶子数、度为1的、度为2的结点数算法;

    25、补充:对于K叉树,其结点总数为N,求出该树的最大高度、高小高度;

    26、补充:构造结点数为n的k叉哈夫曼树(其所有的结点要么度为0,要么度为k),注意一般都需要增加m个权为0的结点(称为虚结点),其中如果叶子结点数目不足以构成正则的k叉树(树中只有度为k或0的结点),即不满足(n-1)MOD(k-1)=0(其中MOD是取余运算),需要添加权为0的结点,添加的个数为m=k-(n-1)MOD(k-1)-1。添加的位置应该是距离根结点的最远处。假设n=10,k=3,则需要添加1个权为0的虚结点(其字母可以为空)。

    第七章 图

    1、图的几个重要概念:顶点、弧、弧尾、弧头、边、有向图、无向图、完全图、邻接点、入度、出度、度、路径、回路(环)、连通图、连通分量、强连通图、强连通分量、生成森林、关节点、重连通图、AOV-网、AOE-网;

    2、图的几种存储、表示方法:数组表示法(重要)、邻接表(最重要,应用最广)、逆邻接表(掌握)、十字链表(理解)、邻接多重表(了解),并能大致掌握他们各种方法表示的优缺点;

    3、图的两种遍历顺序:深度、广度优先,建议同时掌握其算法;

    4、图的生成树和生成森林(只需掌握手画方法);

    5、图的最小生成树的两种算法:普里姆(Prim)算法(实质是顶点优先)、克鲁斯卡尔(Kruskal)算法(实质是边优先),掌握他们的手动构造过程,了解算法;

    6、理解求关节点算法,可见算法7.10、7.11;

    7、了解拓扑排序;

    8、掌握由AOE-网得到关键路径的方法(手动),了解算法(7.13、7.14);

    9、掌握最短路径的手动求解过程、方法(两种:迪杰斯特拉Dijkstra、弗洛伊德Floyd),了解算法;

    10、补充:Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的时间复杂度;

    11、补充:了解拓扑排序算法;

    12、补充:能将图的抽象定义,如有向图G=(V,{A}),V={v1,v2,v3,v4},A={

    展开全文
  • 一个算法必须满足一下五个重要特性。 有穷性:一个算法必须总是在执行有穷步后结束,且每一步都必须在又穷时间内完成。 确定性:对于每种情况下所应执行的操作,在算法中都有确切的规定,不会产生二义性,是算法的...
  • 算法必须满足下列五个重要特性: (1)输入: 一个算法有零或多个输入(即算法可以没有输入),这些输入通常取自某个特定的对象集合。 (2)输出: 一个算法有一或多个输出(即算法必须要有输出),通常输出与输入...
  • 算法及其设计原则

    千次阅读 2018-10-23 10:54:56
    严格说来,一个算法必须满足以下五个重要特性: (1) 有穷性 对于任意一组合法的输入值,在执行有穷步骤之后一定能结束。 (2) 确定性 对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或...
  • 第1章 绪论 1.4 算法与算法分析 算法algorithm的概念 算法是对问题求解过程的一种描述是为解决一个或一类问题给出的一个确定的有限长的操作序列严格说来一个算法必须满足以下五个重要特性 关于本书采用的类语言描述C...
  • 1.2.1 一个算法必须满足以下五个重要特性 有穷性。一个算法必须总是在执行有穷步后结束,且每一步都必须在有穷时间内完成。 确定性。对千每种情况下所应执行的操作,在算法中都有确切的规定,不会产生二义性,使...
  • 数据结构与算法

    2011-04-08 17:09:36
    第一章 数据源和数据项 数据项:数据结构中讨论的最小单位 ...一个算法必须满足以下五个重要特性: 1.有穷性 2.确定性 3.可行性 4.有输入 5.有输出   算法设计的原则 1.正确性 2.可读性 ...
  • Java发送邮件时,必须要的一个配置! fastjson学习笔记 本地文件自动同步到GitHub 为什么PUSH推送经常出事故? 三歪用了10分钟写完了一个需求 :book:Java容器 Java集合总结 【新手向】如何学习Java集合 ...
  • 数据结构-序章(二)

    2019-10-13 16:34:17
    一个算法必须满足以下五个重要特性: 有穷性: 一个算法必须总是在执行有穷步后结束,且每一步都必须在有穷时间内完成。 确定性: 对于每种情况下所应执行的操作,在算法中都有确切的规定,不会产生二义性,使算法...
  • C语言数据结构(二)

    2018-07-14 19:56:00
    一个算法必须满足以下五个重要特性: 1.有穷性 对于任意一组合法输入值,在执行又穷步骤之后一定能结束,即:算法中的每个步骤都能在有限时间内完成; 2.确定性 对于每种情况下所应执行的操作,在算法中都有确切的...
  • 一个算法必须满足以下五个重要特性: 1有穷性 2确定性 3可行性 4有输入 5有输出 1有穷性 对于任意一组合法的输入值,在执行有穷步骤之后一定能结束,即:算法中的每个步骤都能在有限时间内完成;   2.确定性 ...
  • 随着新特性的不断添加,C++一度成为一个活动目标,不过现在有了2003年的ISO/ ANSIC++标准第二版后,已经稳定下来了。现代编译器支持该标准要求的多数或全部特性,程序员要花时间 来习惯这些特性的应用。本书第...
  • 随着新特性的不断添加,C++一度成为一个活动目标,不过现在有了2003年的ISO/ ANSIC++标准第二版后,已经稳定下来了。现代编译器支持该标准要求的多数或全部特性,程序员要花时间 来习惯这些特性的应用。本书第...
  • 随着新特性的不断添加,C++一度成为一个活动目标,不过现在有了2003年的ISO/ ANSIC++标准第二版后,已经稳定下来了。现代编译器支持该标准要求的多数或全部特性,程序员要花时间 来习惯这些特性的应用。本书第...
  • 随着新特性的不断添加,C++一度成为一个活动目标,不过现在有了2003年的ISO/ ANSIC++标准第二版后,已经稳定下来了。现代编译器支持该标准要求的多数或全部特性,程序员要花时间 来习惯这些特性的应用。本书第...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    满足五个基本特性 D.A和 C. 5. 下面关于算法说法错误的是(D )【南京理工大学 2000 、1(1.5分)】 A.算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的...
  • 2,提供一个查询的语言特性。在第一种情况下,并没有类型系统(type system)帮助你对查询进行语义检查。在后一种情况下,类型系统和编译器参与检查确保查询处于良好状态并且不会中断。在过去的十年中,语言集成...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    <br>实验四 综合(课程设计) 内容及步骤: 1、假定一维数组a[n]中的每个元素值均在[0,200]区间内,用C++编写一个算法,分别统计出落在[0,20],[21,50],[51,80],[81,130],[131,200]等各区间内的元素...
  • 软件测试规范

    2018-04-23 09:16:12
    6 .黑盒测试方法 ............................................................................................................................................ 7 1.等价类划分 ...........................
  • Message-Driven Bean EJB实例源代码 2个目标文件 摘要:Java源码,初学实例,EJB实例 Message-Driven Bean EJB实例源代码,演示一个接收购物订单的消息驱动Bean,处理这个订单同时通过e-mail的形式 //给客户发一个感谢...
  • JAVA上百实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     //给客户发一个感谢消息,消息驱动Bean必须实现两个接口MessageDrivenBean和MessageListener  在对象创建的过程中将被容器调用,onMessage函数方法接收消息参数,将其强制转型为合适的消息类型,同时打印出消息...

空空如也

空空如也

1 2 3
收藏数 49
精华内容 19
关键字:

一个算法必须满足五个重要特性