绪论 Overview

主要内容: 1. 数据结构的基本概念; 2. 算法的定义及分析; 3. 抽象数据类型ADT; 4. 时间复杂度O( )

概述 Overview

概念: 数据Data：客观事物的符号表示; 数据元素Data Element：数据的基本单位; 数据项Data Item：数据的最小单位; 数据对象Data Object：性质相同的数据元素的集合
关注: 数据的表示

数据的存储

数据的使用; []如何定制课程表?; [实例]广州工商学院2022年度个人课表-展示效果之一; [实例]广州工商学院2022年度个人课表-原始数据
逻辑结构: 从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的; . 线性结构：一对一; . 树形结构：一对多; . 图结构/网状：多对多; . 集合
存储结构: 数据在计算机中的存储结构，也称物理结构; . 顺序存储结构：存储单元连续，多使用数组实现; . 链式存储结构：存储单元不连续，多使用指针实现

抽象数据类型 ADT

数据类型 Data Type: . 程序设计语言中的一个概念; . 一个值的集合以及定义在这个集合上的一组运算的总称
抽象数据类型 Abstract Data Type: 一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，包括3个部分：; . 数据对象; . 数据对象的关系集合; . 数据对象的基本操作/算法集合; 具备如下特点：; . 抽象化; . 模型化; . 封装化; . 隐蔽化

算法 Algorithm

重要特性: . 有穷性; . 确定性; . 可行性; . 输入; . 输出
基本标准: . 正确性 Corrective; . 可读性 Readable; . 健壮性 Robust; . 高效性 Effective
评价角度: . 空间复杂度：固定存储、可变存储; . 时间复杂度

时间复杂度 Time Complexity

概念

算法中，基本语句重复执行的次数是问题规模n的某个函数f(n)；记作：

T(n) = O(f(n))

随着问题规模n的增加，算法执行时间的增长率和f(n)的增长率相同，称为时间复杂度 - Time Complexity，使用大O表示

焦点

. 问题规模n

. 语句频度

基本步骤

1. 找出执行次数最多的语句，通常是最内层循环的循环体

2. 计算该语句的执行次数和问题规模n的数量级关系

3. 保留Keep最高次幂[关键操作次数的数量级]

4. 舍弃Disregard最高次幂系数

5. 舍弃Disregard低次幂和常数项

6. 当问题规模n达到一定数量级时，其系数和所有低次幂及常数项的影响忽略不计

基本原则

加法：T(n) = T₁(n) + T₂(n) = O( max(f₁(x),f₂(x)) )

乘法：T(n) = T₁(n) * T₂(n) = O( f₁(x) * f₂(x) )

常见时间复杂度O()

常数阶O(1) < 对数阶O(log₂n) < 线性阶O(n) < 线性对数阶O(nlog₂n) < 平方阶O(n²) < 立方阶O(n³)

O(n)

执行次数：n+1；数量级：n；使用等差数列推导

void fn(int n)
{
    int i;
    for (i = 0; i <= n; i++)
    {
        i++;
    }
}

int fn(int n)
{
    if (!n)
        return 1;
    else
        return n * fn(n - 1);
}

O(n²)

关键语句：x++；执行次数：n*n；数量级：n*n

void fn(int n)
{
    int i, j, x = 0;
    for (i = 1; i < n; i++)
    {
        for (j = i + 1; j <= n; j++)
        {
            x++;
        }
    }
}

s = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        s += B[i][j];
sum = s;

O(n³)

关键语句：s++；执行次数：n*n*n；数量级：n*n*n

void fn(int n)
{
    int i, j, k, s;
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= i; j++)
        {
            for (k = 0; k < j; k++)
            {
                s++;
            }
        }
    }
}

O(log₂n)

执行次数没有达到n，而是n的对数阶

void fn(int n)
{
    int i = 0;
    while (i < n)
    {
        i += 2;
    }
}

void fn(int n)
{
    int i = 1;
    while (i <= n)
    {
        i *= 2;//引入中间变量k,令i=2k
    }
}

O(n^1/2)

void fn(int n)
{
    int i = 0, sum = 0;
    while (sum <= n)
    {
        sum += ++i;
    }
}

练习 Quiz

通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（B）。

A. 数据具有同一特点

B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C. 每个数据元素都一样

D. 数据元素所包含的数据项的个数要相等

除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的（B）。

A. 时间效率

B. 空间效率

C. 硬件效率

D. 软件效率

以下说法不正确的是（D）。

A. 线性结构中，数据元素之间存在一对一的关系。

B. 数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

C. 数据项是组成数据元素的、有独立含义的、不可分割的最小单位。

D. 数据的逻辑结构依赖于数据的存储结构。

数据的逻辑结构与数据的存储无关，是独立于计算机的。（√）

分析下面代码时间复杂度O()

A: O(n)

B: O(nlog₂n)

C: O(n²)

D: O(log₂n*log₁₀n)

void fn(int n)
{
    int count = 0, k, j;
    for (k = 0; k <= n; k *= 2)
    {
        for (j = 0; j <= n; j++)
        {
            count++;
        }
    }
}
//核心语句执行次数分别是2的倍数和1的倍数

void fn(int n)
{
    int count = 0, k, j;
    for (k = 0; k <= n; k *= 2)
    {
        for (j = 0; j <= n; j *= 10)
        {
            count++;
        }
    }
}
//核心语句执行次数分别是2的倍数和10的倍数

下列时间复杂度中最坏的是（D）。

A. O(1)

B. O(n)

C. O(log2n)

D. O(n2)

有时为了提高时间复杂度，会增加空间复杂度。因此，算法的时间复杂度和空间复杂度之间是有矛盾的。（√）