数据结构学习笔记(一) - 基本概念
第一章 基本概念
1 数据结构
数据结构没有官方的或统一的定义，各种书籍或资料中对数据结构的定义都不完全相同，但是可以发现数据结构和算法总是同时被提及，那么应该如何定义数据结构？通过以下三个例子来理解：
如何在书架上摆放图书
图书的摆放要使得两个相关操作方便实现：
能够想到三种方法：
结论：解决问题方法的效率，跟数据的组织方式有关
依次摆放：方便插入新书，但是难以找到指定的书
按书名的拼音字母顺序摆放：方便找到指定的书，但是难以插入新书
把书架划分为几块区域，每个区域中摆放指定类别的图书，在每种类别中按照书名的拼音字母顺序摆放：方便插入和查找，但是如何划分类别，每种类别分配多大的书架
新书怎么插入
怎么找到指定的书
实现一个
printN函数，接受一个正整数 NNN 作为参数，能够顺序打印从 111 到 NNN 的全部正整数以上两种实现代码量几乎相同，在参数 NNN 数值较小时效果也几乎相同，但是当 NNN 大到一定程度时，递归实现会报错。在开发过程中，递归的思路比较容易想到，实现也比较简单，但是递归的实现对空间的占用更大。
结论：解决问题方法的效率，跟空间的利用效率有关
循环实现
function printN(N: number): void { for (let i = 1; i <= N; i++) { console.log(i) } } 复制代码递归实现
function printN(N: number): void { if (N > 0) { printN(N - 1) console.log(N) } } 复制代码实现一个计算给定多项式在给定点 xxx 处的值
以上两种实现的代码量也几乎相同，但第一种实现所用时间比第二种多了一个数量级。
结论：解决问题方法的效率，跟算法的巧妙程度有关
直接的实现
function compute(n: number, a: Array<number>, x: number): number { let p: number = a[0] for (let i = 1; i <= n; i++) { p += (a[i] * Math.pow(x, i)) } return p } 复制代码提取公因式后的实现
function compute(n: number, a: Array<number>, x: number): number { let p: number = a[n] for (let i = n; i > 0; i--) { p = a[i - 1] + x * p } return p } 复制代码
数据结构：
数据对象在计算机中的组织方式
逻辑结构：线性结构和树形结构
物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
抽象数据类型（Abstract Data Type）：用于描述数据结构的方法，只描述数据对象集和相关操作集是什么，并不涉及如何做到的问题。
数据类型
数据对象集
数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言无关
例：矩阵的抽象数据类型定义
create(M: number, N: number): Matrix：返回一个 M×NM×NM×N 的空矩阵getMaxRow(A: Matrix): number：返回矩阵 A 的总行数getMaxCol(A: Matrix): number：返回矩阵 A 的总列数getEntry(A: Matrix, i: number, j: number): ElementType：返回矩阵 A 的第 iii 行、第 jjj 列的元素add(A: Matrix, B: Matrix): Matrix：返回矩阵相加的结果multiply(A: Matrix, B: Matrix): Matrix：返回矩阵相乘的结果类型名称：矩阵（
Matrix）数据对象集：一个 M×NM×NM×N 的矩阵 A 由 M×NM×NM×N 个三元组 <a,i,j><a, i, j><a,i,j> 构成，其中 aaa 是元素的值，iii 是元素所在的行号，jjj 是元素所在的列号。
操作集：
2. 算法
算法（Algorithm）
有充分明确的目标，不可以有歧义
计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现手段
一个有限指令集
接受一些输入（有些情况下不需要输入）
产生输出
一定在有限步骤后终止
每一条指令必须
例：选择排序算法的伪码描述
function SelectionSort(list, n) { for (i: 0 -> n) { /* 从 list[i] 到 list[n - 1] 中找最小元，并将其位置付给 minPosition */ minPosition = scanForMin(list, i, n - 1) /* 将未排序部分的最小元换到有序部分的最后位置 */ swap(list[i], list[minPosition]) } } 复制代码什么是好的算法
在解决同一个问题的时候，通常会有很多种不一样的算法，区别在于有的算法比较“笨”，而有的算法比较“聪明”，通常利用空间复杂度和时间复杂度这两个指标来评判一个算法的好坏：
在分析算法的效率时，经常关注最坏情况复杂度 Tw(n)T_w(n)Tw(n)和平均复杂度 Ta(n)T_a(n)Ta(n)，平均复杂度一般难以确定，因此通常关心最坏情况复杂度。
时间复杂度 S(n)S(n)S(n)：根据算法写成的程序在执行时占用存储单元的数量
空间复杂度 T(n)T(n)T(n)：根据算法写成的程序在执行时耗费时间的长度
复杂度的渐进表示法
过大的上界或过小的下界都没有意义，对于分析问题没有帮助，因此需要找到最接近真实情况的上界和下界。
T(n)=O(f(n))T(n) = O (f(n))T(n)=O(f(n)) 表示存在常数 C>0C \gt 0C>0，n0>0n_0 \gt 0n0>0 使得当 n≥n0n \geq n_0n≥n0 时有 T(n)≤C⋅f(n)T(n) \leq C \cdot f(n)T(n)≤C⋅f(n) （简而言之，O(f(n))O(f(n))O(f(n)) 表示 f(n)f(n)f(n) 是 T(n)T(n)T(n) 的某种上界，对于充分大的 nnn 而言）
T(n)=Ω(f(n))T(n) = \Omega (f(n))T(n)=Ω(f(n))表示存在常数 C>0C \gt 0C>0，n0>0n_0 \gt 0n0>0 使得当 n≥n0n \geq n_0n≥n0 时有 T(n)≥C⋅f(n)T(n) \geq C \cdot f(n)T(n)≥C⋅f(n) （简而言之，Ω(f(n))Ω(f(n))Ω(f(n)) 表示 f(n)f(n)f(n) 是 T(n)T(n)T(n) 的某种下界，对于充分大的 nnn 而言）
T(n)=Θ(f(n))T(n) = \Theta (f(n))T(n)=Θ(f(n)) 表示同时有 T(n)=O(f(n))T(n) = O (f(n))T(n)=O(f(n)) 和 T(n)=Ω(f(n))T(n) = \Omega (f(n))T(n)=Ω(f(n)) （简而言之，Θ(f(n))Θ(f(n))Θ(f(n)) 与 f(n)f(n)f(n) 等价的，对于充分大的 nnn 而言）
复杂度分析技巧
T1(n)+T2(n)=max(O(f1(n)),O(f2(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)))
T1(n)×T2(n)=O(f1(n)×f2(n))T_1(n) \times T_2(n) = O(f_1(n) \times f_2(n))T1(n)×T2(n)=O(f1(n)×f2(n))
若两段算法分别由复杂度 T1(N)=O(f1(n))T_1(N) = O(f_1(n))T1(N)=O(f1(n)) 和 T2(n)=O(f2(n))T_2(n) = O(f_2(n))T2(n)=O(f2(n))，则
若 T(n)T(n)T(n) 是关于 nnn 的 kkk 阶多项式，那么 T(n)=Θ(nk)T(n) = \Theta (n^k)T(n)=Θ(nk)
一个
for循环的时间复杂度等于循环次数乘以循环体代码的复杂度if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中的最大值
3. 实例：最大子列和
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。（力扣_第53题）
暴力法：时间复杂度 O(n3)O(n^3)O(n3)
暴力法的简单优化：时间复杂度 O(n2)O(n^2)O(n2)
分治：时间复杂度 O(nlog(n))O(n \log (n))O(nlog(n))
在线处理：时间复杂度 O(n)O(n)O(n)
作者：Stan9726
链接：https://juejin.cn/post/7018914460655943688