数据结构之概述(数据和算法基本概念，时间复杂度)

╰半橙微兮° 2022-06-17 00:00 192阅读 0赞

### 基本概念 ###

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

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

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

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

**数据结构**： 一个有穷的结点集合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)

*  分层计算法：若一段程序出现多重循环，或循环体中调用了函数，而被调函数中又带有循环，即还有多个层次，可以分别计算各层时间耗费，然后相乘，其乘积作为该段程序的时间复杂性。
 *  递推式方法：根据递推方程式计算。
 *  数学模型法：暂无。