一、数据结构

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 w o r s t ( n ) _{worst}(n) worst(n)

    • 平均情况复杂度 T a v g ( n ) _{avg}(n) avg(n)

      T a v g ( n ) T w o r s t ( n ) T_{avg}(n) ≤ T_{worst}(n) Tavg(n)Tworst(n)

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

4. 复杂度的渐进表示法

  • T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n)) 表示存在常数 C>0, n 0 n_0 n0>0,使得当 n n 0 n≥n_0 nn0 时有 T ( n ) C f ( n ) T(n) ≤C·f(n) T(n)Cf(n),即 O ( f ( n ) ) O(f(n)) O(f(n))表示 f ( n ) f(n) f(n) 是 T(n) 的某种上界
  • T ( n ) = Ω ( g ( n ) ) T(n) = Ω(g(n)) T(n)=Ω(g(n)) 表示存在常数 C>0, n 0 n_0 n0>0,使得当 n n 0 n≥n_0 nn0 时有 T ( n ) C g ( n ) T(n) ≥C·g(n) T(n)Cg(n),即 Ω ( g ( n ) ) Ω(g(n)) Ω(g(n)) 表示 g ( n ) g(n) g(n) 是 T(n) 的某种下界
  • T ( n ) = θ ( h ( n ) ) T(n) = θ(h(n)) T(n)=θ(h(n)) 表示同时有 T ( n ) = O ( h ( n ) ) T(n) = O(h(n)) T(n)=O(h(n)) T ( n ) = Ω ( h ( n ) ) T(n) = Ω(h(n)) T(n)=Ω(h(n)),即 θ ( h ( n ) ) θ(h(n)) θ(h(n)) 既是上界也是下界

5. 复杂度分析小窍门

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

课后编程题题解

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