一、基本概念

1. 数据

数据（Data）是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
例如：文本、图像、视频、等。

2. 数据元素

数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
相当于数据库中表的概念，例如在学生表中需要有学号、姓名、班级、年龄等信息作为一个在学校学习的人的记录。

3. 数据项

数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
如上：学生中学号、姓名、班级、年龄这些信息，都是原子性的。

4. 数据对象

数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。
即是多个数据元素的集合，称之为数据对象。
不支持在 Docs 外粘贴 block

二、数据结构

数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

1、逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构描述的是数据元素之间的逻辑关系。

• 集合结构
  数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看作一个集合结构。
• 线性结构

数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。

• 树结构

数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。

• 图结构

数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构或网状结构。
不支持在 Docs 外粘贴 block

2、存储结构（物理结构）

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。
数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。
顺序存储结构
逻辑关系：通过每个数据元素的相对的位置表示元素之间的逻辑关系
存储元素：要求所有的元素存放在一片连续的连续空间中。

链式存储结构
逻辑关系：通过指针指向后继节点存储地址。
存储元素：无需顺序存储但是需要保存后继节点存储地址。

三、数据类型和抽象数据类型

1、数据类型
2、抽象数据类型

四、算法

1、算法

• 什么是算法

为了解决某类问题而规定的一个有限长的操作序列。

• 需要满足条件
  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出
• 算法优劣性
  • 正确性
  • 可读性
  • 健壮性
  • 高效性

2、时间复杂度

事前分析估算法

• 问题规模

问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。问题规模n对不同的问题含义不同
一个算法的执行时间大致上等于其所有语句执行时间的总和
语句的执行时间 = 该条语句的重复执行次数 * 执行一次所需时间。

• 语句频度

一条语句的重复执行次数称作语句频度（Frequency Count）。

• 算法执行时间

设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。

时间复杂度

用算法中的“基本语句”（算法中重复执行次数和算法的执行时间成正比的语句）的执行次数来度量算法的工作量。
如上面的例子，f(n) = 2n^3+3n^2+2n+1当n->∞时，f(n) = n^3。用O表示数量级，记作T(n)=O(f(n))=O(n3)。所以算法的复杂度可以记作：
T(n) = O(n3)
分析时间复杂度的基本方法
找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)，取其数量级用符号“O”表示即可

• 定理1.1
  • 若f(n)=amn^m+anm-1+…+a1n+a0是一个m次多项式，则T(n)=O(n^m)。

在计算算法时间复杂度时，可以忽略所有低次幂项和最高次幂的系数，这样可以简化算法分析，也体现出了增长率的含义。

案例1、时间复杂度案例说明

1. 常量阶

public void demo(){
    x++;
    s = 0;
}
复制代码

T(n) = O(1)
复制代码

2. 线性阶

public void demo(){
    for(int i = 0 ; i < 10000 ; i++){
        x++;
        s = 0;
    }
}
复制代码

T(n) = O(1)
复制代码

3. 平方阶

在下面代码中，有两个频度一个n，一个是n^2。所以最大频度的语句是8行内的语句，时间复杂度为O(n^2)

public void demo(){
    for(int i = 0 ; i < n; i++){
        y++;
    }

    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < i ; j++){
            x++;
            s = 0;
        }
    }
}
复制代码

T(n) = O(n^2)
复制代码

4. 立方阶

for(int i = 0 ; i < n; i++){
    for(int j = 0; j < i ; j++){
        for(int x = 0; x < j ; x++){
            x++;
        }
    }
}

T(n) = O(n^3)
复制代码

5. 对数阶

for(int x = 0; x < n ; x*2){
    x++;
}
复制代码

T(n) = O(log2N)
复制代码

4、空间复杂度

空间复杂度（Space Complexity）作为算法所需存储空间的量度，简称空间复杂度，它也是问题规模n的函数，记作:

S(n)=O(f (n))
复制代码

案例2、空间复杂度案例说明

for(int i = 0; i < n/2 ; i++){
    t = a[i];
    a[i] = a[a - i -1];
    a[n - i - 1] = t;
}
复制代码

需要另外借助一个变量t，与问题规模n大小无关，所以其空间复杂度为O(1)。
S(n)=O(1)

for(i = 0 ; i < n ; i ++){
    b[i] = a[a - i -1];
}

for(i = 0 ; i < n ; i ++){
    a[i] = b[i];
}
复制代码

需要另外借助一个大小为n的辅助数组b，所以其空间复杂度为O(n)。
S(n)=O(n)