关于数据组织 #
笔记 #
具象例子：
- 如何在书架上摆放图书:把书架划分为几块区域，每块区域指定拜访某种类别的书，每个类别内用书名的拼音排序
问题：①如何分配空间？②类别要分多细？
结论：解决问题方法的效率与数据的组织方式有关。
关于空间使用 #
笔记 #
案例问题：实现一个函数，输入一个正整数N后可以顺序打印从1到N的全部正整数。
循环实现： #
//循环实现
static void PrintN(int N)
{
int i = 1;
for (i = 1; i <= N; i++)
{
Console.Write(i);
}
}递归实现： #
//递归实现
static void PrintN(int N)
{
if (N>0)
{
PrintN(N - 1);
Console.Write(N);
}
}令N=100，1000，10000，100000…分别测试两种实现方式的效果：
前面都没事差不多，但是在100000时，递归就罢工了。
递归的程序对空间的占用有时会过多。
结论：解决问题方法的效率和空间的利用效率有关
关于算法效率 #
笔记 #
案例问题：写程序计算给定多项式在给定点x处的值
多项式（打这个用了[[Latex语法]]）：$f(x)=a_{0}+a_{1}x+···+a_{n-1}x^{n-1}+a_{n}x^{n}$
//不好的写法
static double F(int n, double a[], double x)
{
int n=1;
double fx=a[0];
for(i=1,i<=n,i++)
{
fx +=(a[i]*pow(x,i));
}
return fx;
}计算前首先把多项式换个形式:
$$f(x)=a_{0}+x(a_{1}+x(…(a_{n-1}+x(a_{n}))…))$$
//更好的写法
static double F(int n, double a[], double x)
{
int i;
double fx=a[n];
for(i=n,i>0,i--)
{
fx=a[i-1]+x*p;
}
return fx;
}结论：解决问题方法的效率，和算法的巧妙程度有关
抽象数据类型 #
笔记 #
数据结构是数据对象在计算机中的组织方式
- 逻辑结构
- 线性结构
- 树形结构
- 图形结构
- 物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
抽象数据类型（Abstract Data Type）
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。
数据类型：
- 数据对象集
- 数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言无关
例：“矩阵”的抽象数据类型定义(其中何种矩阵、元素是何种数据类型、具体实现方法、语言均为抽象)
- 类型名称：矩阵（Matrix）
- 数据对象集：一个$M\times N$的矩阵$A_{M\times N}=(a_{ij})(i=1,…,M;j=1,…,N)$由$M\times N$个三元组$$构成，其中$a$是矩阵元素的值，$i$是元素所在的行号，$j$是元素所在的列号。
- 操作集：对于任意矩阵$A、B、C\in Matrix$,以及整数$i、j、M、N$
- Matrix Create(int M, int N):返回一个$M\times N$的空矩阵
- int GetMaxRow(Matrix A):返回矩阵A的总行数
- int GetMaxCol(Matrix A):返回矩阵A的总列数
- ElementType GetEntry(Matrix A, int i, int j):返回矩阵A的第一行、第j列的元素
- Matrix Add(Matrix A, Matrix B):如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志
- Matrix Multiply(Matrix A, Matrix B):如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志
- …
算法的定义 #
笔记 #
算法（Algorithm）
- 一个有限指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能够处理的范围之内
- 描述应不依赖于任何一种计算机语言以及具体的实现手段
例1：选择排序算法的伪码描述
void SelectionSort(int List[], int N)
{
/*将N个整数List[0]...List[n-1]进行非递减排序*/
从List[i]到List[n-1]中找最小元，并将其位置赋给MinPosition;
将未排序部分的最小元换到有序部分的最后位置
}抽象：
List到底是数组还是链表？
切换位置用函数/宏都可以
什么是好的算法 #
笔记 #
衡量算法的指标： #
空间复杂度$S(n)$ #
根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
$S(n)=C\times N$
时间复杂度$T(n)$ #
根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致运行花费太久的时间。
(可以通过算机器做了几次乘除法来判断)
什么是好的算法？ #
- 在分析一般算法的效率时，经常关注下面两种复杂度
- 最坏情况复杂度$T_{worst}(n)$
- 平均复杂度$T_{avg}(n)$
$T_{avg}(n)\leqslant T_{worst}(n)$
分析平均复杂度比较难，更关心最坏情况复杂度
复杂度的渐进表示 #
笔记 #
复杂度的渐进表示法
- 算法的上界：$T(n)=O(f(n))$表示存在常数$C>0,n_{0}>0$使得当$n\geq n_{0}$时有$T(n)\leqslant C\cdot f(n)$
- 算法的下界：$T(n)=\Omega(g(n))$表示存在常数$C>0,n_{0}>0$使得当$n\geq n_{0}$时有$T(n)\geq C\cdot g(n)$
- $T(n)=\Theta(h(n))$表示同时有$T(n)=O(h(n))$和$T(n)=\Omega(h(n))$
不同函数根据输入规模n的变化复杂度的变化：
【输入规模变化图1】
【输入规模变化图2】
复杂度分析小窍门 #
- 若两端算法分别有复杂度$T_{1}(n)=O(f_{1}(n))$和$T_{2}(n)=O(f_{2}(n))$，则
- $T_{1}(n)+T_{2}(n)=max(O(f_{1}(n)),O(f_{2}(n)))$
- $T_{1}(n)\times T_{2}(n)=O(f_{1}(n)\times f_{2}(n))$
- 若$T(n)$是关于n的k阶多项式，那么$T(n)=\theta(n^{k})$
- 一个循环结构的时间复杂度等于循环次数乘以循环体代码的复杂度
- if else语句结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大
应用实例-最大子列和问题 #
应用实例-题目 #
给定N个整数的序列$\left{A_1,A_2,…,A_N \right}$,求函数$f(i,j)=max\left{0,\sum_{k=i}^{j}A_K\right}$的最大值
应用实例-算法一【复杂度$T(N)=O(N^3)$】： #
int MaxSubseqSum(int A[], int N)
{
int ThisSum, MaxSum=0;
int i,j,k;
for(i=0;i<N;i++)
{
for(j=i;j<N;j++)
{
ThisSum=0;
for(k=i;k<=j;k++)
{
ThisSum+=A[k];
if(ThisSum>MaxSum)
MaxSum=ThisSum;
}
}
}
return MaxSum;
}应用实例-算法2【复杂度$T(N)=O(N^2)$】： #
int MaxSubseqSum2(int A[],int N)
{
int ThisSum,MaxSum=0;
int i,j;
for(i=0;j<N;i++)
{
ThisSum=0;
for(j=i;j<N;j++)
{
ThisSum+=A[j];
if(ThisSum>MaxSum)
MaxSum=ThisSum;
}
}
return MaxSum;
}应用实例-算法3：分而治之 #
笔记 #
【分而治之图】
应用实例-算法4：在线处理 #
笔记【复杂度$T(N)=O(N)$】 #
int MaxSubseqSum4(int A[],int N)
{
int ThisSum,MaxSum;
int i;
ThisSum=MaxSum=0;
for(i=0;i<N;i++)
{
ThisSum+=A[i];//向右累加
if(ThisSum>MaxSum)
MaxSum=ThisSum;//发现更大和则更新当前结果
elseif(ThisSum<0)//如果当前子列和为负
ThisSum=0;//则不可能使后面的部分和增大，抛弃原有结果
}
return MaxSum;
}“在线”指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。
