数据结构（一）基本概念

一、数据结构

1. 其他定义

• 数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。 ——Sartaj Sahni 《数据结构、算法与应用》
• 数据结构是 ADT（Abstract Data Type，数据抽象类型）的物理实现。 ——Clifford A.Shaffer 《数据结构与算法分析》
• 数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。 ——中文维基百科

2. 解决问题方法的效率

• 跟数组的组织方式有关
• 跟空间的利用效率有关
• 跟算法的巧妙程度有关

3. 最终定义

• 数据对象在计算机中的组织方式
  • 逻辑结构
  • 物理存储结构
• 数据对象必定与一系列加在其上的操作相关联
• 完成这些操作所用的方法就是算法

4. 抽象数据类型（Abstract Data Type）

• 数据类型
  • 数据对象集
  • 数据集合相关联的操作集
• 抽象：描述数据类型的方法不依赖于具体实现
  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

二、算法

1. 定义

• 一个有限指令集
• ≥ 0 的输入
• $\>$>​ 0 的输出
• 一定在有限步骤之后终止
• 每一条指令必须
  • 有充分明确的目标，不可以有歧义
  • 计算机能处理范围内
  • 描述应不依赖于任何一种计算机语言以及具体的实现手段

2. 描述算法的手段

1. 空间复杂度 S(n)

   根据算法写成的程序在执行时占用存储空间的长度

2. 时间复杂度 T(n)

   根据算法写成的程序在执行时耗费的时间的长度

3. 评价

• 在分析一般算法的效率时，常常关注

  • 最坏情况复杂度 T ${worst}_{}\left(n\right)$worst​(n)

  • 平均情况复杂度 T ${avg}_{}\left(n\right)$avg​(n)

    $T_{avg}\left(n\right)\le T_{worst}\left(n\right)$Tavg​(n)≤Tworst​(n)

  一般情况下更多关注的是最坏情况复杂度

4. 复杂度的渐进表示法

• $T\left(n\right)=O\left(f\right(n\left)\right)$T(n)=O(f(n)) 表示存在常数 C>0， $n_0$n0​>0，使得当 $n\ge n_0$n≥n0​ 时有 $T\left(n\right)\le C\cdot f\left(n\right)$T(n)≤C⋅f(n)，即 $O\left(f\right(n\left)\right)$O(f(n))表示 $f\left(n\right)$f(n) 是 T(n) 的某种上界
• $T\left(n\right)=\Omega \left(g\right(n\left)\right)$T(n)=Ω(g(n)) 表示存在常数 C>0， $n_0$n0​>0，使得当 $n\ge n_0$n≥n0​ 时有 $T\left(n\right)\ge C\cdot g\left(n\right)$T(n)≥C⋅g(n)，即 $\Omega \left(g\right(n\left)\right)$Ω(g(n)) 表示 $g\left(n\right)$g(n) 是 T(n) 的某种下界
• $T\left(n\right)=\theta \left(h\right(n\left)\right)$T(n)=θ(h(n)) 表示同时有 $T\left(n\right)=O\left(h\right(n\left)\right)$T(n)=O(h(n)) 和 $T\left(n\right)=\Omega \left(h\right(n\left)\right)$T(n)=Ω(h(n))，即 $\theta \left(h\right(n\left)\right)$θ(h(n)) 既是上界也是下界

5. 复杂度分析小窍门

• 若两段算法分别有复杂度 $T_1\left(n\right)=O\left(f_1\right(n\left)\right)$T1​(n)=O(f1​(n)) 和 $T_2\left(n\right)=O\left(f_2\right(n\left)\right)$T2​(n)=O(f2​(n))，则
  • $T_1\left(n\right)+T_2\left(n\right)=max\left(O\right(f_1\left(n\right)),O(f_2\left(n\right)\left)\right)$T1​(n)+T2​(n)=max(O(f1​(n)),O(f2​(n)))
  • $T_1\left(n\right)\times T_2\left(n\right)=O\left(f_1\right(n)\times f_2(n\left)\right)$T1​(n)×T2​(n)=O(f1​(n)×f2​(n))
• 若 $T\left(n\right)$T(n) 是关于 $n$n 的 $k$k 阶多项式，那么 $T\left(n\right)=\theta \left(n^k\right)$T(n)=θ(nk)
• 一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度
• if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大

课后编程题题解

最大子列和问题
Maximum Subsequence Sum
二分查找