Skip to content

Latest commit

 

History

History
231 lines (133 loc) · 6.55 KB

1_概述.md

File metadata and controls

231 lines (133 loc) · 6.55 KB
Raw

概述

基本概念

1. 数据

数据是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符合的总称。例如，整数、实数和字符串都是数据。

2. 数据元素

数据元素时数据的基本单位，在计算机程序中通常将其作为一个整体进行考虑或处理。一个数据元素可以由若干个数据项组成。

3. 数据项

数据项是数据结构中讨论的最小单位，是数据记录中最基本的、不可分的数据单位。

4. 数据对象

数据对象是性质相同的数据元素的集合，是数据的一个子集。

5. 数据结构

数据结构是指相互之间存在的一种或多种特定关系的数据元素的集合。数据结构包含3方面的内容：逻辑结构、存储结构和对数据的运算。

6. 数据的逻辑结构

数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。

数据的逻辑结构主要有以下两类：

（1）线性结构

线性结构是一个数据元素的有序集合，主要有以下四个基本特征：

  • 集合中必须存在唯一的一个“第一个元素”
  • 集合中必须存在唯一的一个“最后一个元素”
  • 除了最后一个元素之外，其它数据元素均有唯一的“后继”
  • 除了第一个元素之外，其它数据元素均有唯一的“前驱”

数据结构中线性结构是指数据元素之间存在着“一对一”的线性关系的数据结构。

（2）非线性结构

与线性结构不同，非线性结构中结点存在着一对多的关系，它又可以细分为树形结构和图形结构。

7. 数据的物理结构

也就是存储结构，是数据的逻辑结构在计算机中的表示（又称映像）。它包含数据元素的表示和关系的表示。当数据元素时由若干数据项构成的时候，数据项的表示称为数据域。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。对应两种不同的存储结构分别是顺序存储结构和链式存储结构。

在数据结构中有以下四种常用的存储方法：

（1）顺序存储方法

逻辑上相邻的两个结点存储在屋里位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。

（2）链式存储方法

不要求逻辑上相邻的结点在屋里位置上也相邻，结点间的逻辑关系由附加的指针字段表示。

（3）索引存储方法

在存储结点信息时，除建立结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式<关键字，地址>。关键字标识唯一一个结点，地址作为指向结点的指针。

（4）散列存储方法

根据结点的关键字通过散列函数直接计算出该结点的存储地址。

算法的基本概念

1. 算法

算法可以理解为由基本运算及规定的运算顺序所组成的完整的解题步骤，或者是看成按照要求设计好的有限的确切的计算序列。

2. 算法的特性

  • 有穷性：必须保证执行有限步之后结束
  • 确定性：每一步必须有确定的定义
  • 输入：有0个或多个输入
  • 输出：有一个或多个输出
  • 可行性：所有操作必须可以通过已经实现的基本操作进行运算

3. 算法的设计目标

  • 正确性
  • 可读性
  • 健壮性
  • 算法效率

算法时间复杂度分析

将算法中基本操作的执行次数作为算法时间复杂度的度量。

n：表示数据规模；

O(f(n))：表示运行算法所要执行的指令数，和 f(n) 成正比；

常见的各种复杂度的大小，常用的比较关系：

O(n) <= O(log(n)) <= O(n) <= O(nlog(n)) <= O(n2)<=O(n3)<=O(nk)<=O(2k)

计算一个算法的时间复杂度的具体步骤如下：

（1）确定算法中的基本操作以及问题的规模

（2）根据基本操作执行情况计算出规模 n 的函数 f(n)，确定时间复杂度

基本操作：即其重复执行次数和算法的执行时间成正比的操作。通俗地说，这种操作组成了算法，当它们都执行的时候算法也就结束了，大多数情况下取最深层循环内的语句所描述的操作为基本操作。

示例 1

  • 代码
public void fun(int n){
	int i=1,j=100;
    while(i<n){
        ++j;
        i+=2;
    }
}
  • 分析

（1）确定算法中的基本操作以及问题的规模：

  • 基本操作显然是 ++j 和 i+=2
  • 问题规模，由循环条件 i<n 可以知道，为 n

（2）计算出 n 的函数 f(n)：

假设 i 自增经过 m 次后循环结束，则 i 的最终值为 1+2m ，取一个常数 K，用来进行修正，即

1+2m+K=n （因为 1+2m 不一定刚好等于 n，所以使用一个常数 K 进行修正）。

则 m=(n-1-K)/2 ，f(n)=(n-1-K)/2 （其中，K为常数）。

因此时间复杂度为 O(n)。

示例 2

  • 代码
public void func(int n){
    int i,j,x=0;
    for(i=1;i<n;++i){
        for(int j=i+1;j<=n;j++){
            ++x;
        }
    }
}
  • 分析

（1）确定算法中的基本操作以及问题的规模：

  • 基本操作显然是 ++x
  • 问题规模，由循环条件 i<n 可以知道，为 n

（2）计算出 n 的函数 f(n)：

i=1 时，++x 执行(n-1) 次

i=2 时，++x 执行(n-2) 次

...

i=(n-1) 时，++x 执行 1 次

f(n)=(n-1)+(n-2)+...+1 = n(n-1)/2。

时间复杂度为 O(n^2)。

示例 3

  • 代码
public void func(int n){
    int i=0,s=0;
    while(s<n){
        ++i;
        s=s+i;
    }
}
  • 分析

（1）确定算法中的基本操作以及问题的规模：

  • 基本操作显然是 ++i 和 s=s+i;
  • 问题规模，由循环条件 s<n 可以知道，为 n

（2）计算出 n 的函数 f(n)：

假设循环执行 m 次结束：

m=1 时，s=0+1=1;

m=2 时，s=(1)+2=3;

m=3 时，s=(1+2)+3=6;

...

则 m=m时，s=m(m+1)/2

则有 m(m+1)/2 +K = n （因为 m(m+1)/2 不一定刚好等于 n，所以使用一个常数 K 进行修正）。

由求根公式计算

m =(-1+sqet(8n+1-8K))/2

时间复杂度为 O(sqrt(n))。

算法空间复杂度分析

算法的空间复杂度指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间的大小。

算法原地工作是指算法所需辅助空间是常量，即 O(1)。