
#import "../template.typ": *
#import "@preview/pinit:0.1.4": *
#import "@preview/fletcher:0.5.0" as fletcher: diagram, node, edge
#import "/book.typ": book-page

#show: book-page.with(title: "绪论 | DSA")

= 绪论

== 基本概念

#definition[
  - *数据*：所有能输入到计算机中，且能被计算机程序处理的符号的总称。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。
  - *数据元素*：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。可由若干个数据项组成。
  - *数据项*：是数据结构中讨论的最小单位。数据元素可以是数据项的集合。
  - *数据对象*：是性质相同的数据元素的集合，是数据的一个子集。
  - *数据结构*：带结构的数据元素的集合。是相互之间存在一种或多种特定关系的数据元素的集合。或者说，数据结构是相互之间存在着某种*逻辑关系*的数据元素的集合。
]<基本概念>

四种*逻辑结构*<逻辑结构>：线性结构、树形结构、图形结构或网状结构、集合结构。

// #notefig("../assets/2024-06-12-21-20-53.png")

#definition[
  数据的*存储结构*：逻辑结构在存储器中的映象。
]

- 数据元素的映象方法：如用二进制位串表示。
- 关系的映象方法：
  + *顺序映象*：以相对的存储位置表示后继关系。整个存储结构中只含数据元素本身的信息，其存储位置由隐含值确定。
  + *链式映象*：以附加信息（指针）表示后继关系。需要用一个和 x 在一起的附加信息指示 y 的存储位置。

== 抽象数据类型

#definition[
  *抽象数据类型（#underline[A]bstract #underline[D]ata #underline[T]ype, ADT）*：是指一个数学模型以及定义在此数学模型上的一组操作。
]

描述方法：可用三元组 $(D, S, P)$ 描述。
- 其中 $D$ 是数据对象；
- $S$ 是 $D$ 上的关系集；
- $P$ 是对 $D$ 的基本操作集。

== 算法和算法分析

#definition[
  *算法*：算法是为了解决某类问题而规定的一个有限长的操作序列。
]
算法必须满足以下五个特性：<算法的特性>
+ *有穷性*：算法中的每个步骤都能在有限时间内完成。
+ *确定性*：算法中的每一步都有确切的含义，不会出现二义性。
+ *可行性*：算法中的所有操作都必须足够基本，能够通过已经实现的基本运算执行。
+ *有输入*：算法必须有零个或多个输入。
+ *有输出*：算法必须有一个或多个输出。

算法设计的四个原则：
+ *正确性*
+ *可读性*
+ *健壮性*
+ *高效率与低存储量需求*

== 算法复杂性分析
<算法复杂性分析>
#definition[
  *时间复杂度*：是指算法的运行时间与问题规模之间的关系。
]

#definition[
  *空间复杂度*：是指算法的存储空间与问题规模之间的关系。
]

$O(n)$按数量级递增顺序排列：<常见时间复杂度>

#grid(
  rows: 2,
  row-gutter: 1em,
  columns: 1,

)[
  #set text(size: 8pt)
  *复杂度低* #h(1fr) *复杂度高*
  #v(-0.5em)

  #pin(1) #h(1fr) #pin(2)

  #pinit-arrow(1, 2)
  #v(-1em)

][
  #table(
    align: center + horizon,
    stroke: none,
    columns: (1fr, auto, 1fr, auto, 1fr, 1fr, auto, auto, 1fr),
    table.header(
      [*常数阶*],
      [*对数阶*],
      [*线性阶*],
      [*线性对数阶*],
      [*平方阶*],
      [*立方阶*],
      [*…*],
      [*k 次方阶*],
      [*指数阶*],
    ),

    [$O(1)$], [$O(log n)$], [$O(n)$], [$O(n log n)$], [$O(n^2)$], [$O(n^3)$], [$dots$], [$O(n^k)$], [$O(2^n)$],
  )
]

分析方法：算法的运行时间由程序中所有语句的*频度*（即该语句重复执行的次数）*之和*构成。

#note_block[
  *算法的时间复杂度由嵌套最深层语句的频度决定。*
]




