一. 基本概念
先来一下数据结构中基本的概念。
- 数据
数据是客观事物的符号表示。在计算机学科中指的是所有能输入到计算机中被计算机程序处理的符号的总称。
- 数据元素
数据元素是数据的基本单位。在程序中通常作为一个整体进行考虑和处理。
- 数据项
一个数据元素可由若干个数据项组成。数据项是数据不可分割的最小单位。
- 数据对象
数据对象是性质相同的数据元素的集合，是数据的一个子集。
- 数据结构
指相互之间存在一定关系的数据元素的集合。
- 逻辑结构
元素之间的相互关系称为逻辑结构。逻辑结构有四种基本类型：集合、线性结构、树形结构、图形（网状）结构。如图：
- 物理结构
数据结构在计算机内存中的存储包括数据元素的存储和元素之间关系的存储，元素之间关系的存储称为物理结构。
物理结构有两种不同的存储结构。分别为顺序存储结构和链式存储结构。
顺序结构：数据元素存放的地址是连续的。
连式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的，算法的设计取决于采用的逻辑结构，算法的实现依赖于采用的物理结构。
下图描述了数据逻辑结构的层次关系：
二. 算法分析。
- 算法的设计要求：
正确性
健壮性
可读性
时间效率高和存储量低 - 大O表示法的规则
通常分析算法的时间复杂度和空间复杂度，使用大O表示法。规则如下：
(1) 用常数1表示运行时间中的常数。
(2) 表示运行时间的运算中，只保留最高阶项。
(3) 如果在最高阶存在且不等于1，则去除这个项目相乘的常数
- 时间复杂度分析
时间复杂度有：
常数阶：O(1)
线性阶：O(n)
对数阶：O(*log*n)
线性对数阶：O(n*log*n)
k次方阶：O(n^k)
下图用横轴代表n，纵轴代表执行时间复杂度，我们分析算法的时间复杂度往往是按照最坏情况来考虑，当n趋向无穷大的时候，可以看出以上几种表达式的时间复杂度的大小：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
下面来看几个例子：
- 以下时间复杂度：
O(1)，因为x和y都是常数。
int x=90;
int y=100;
while(y>0){
if(x>100) {
x=x-10;
y--;
}else{
x++;
}
}
- 以下时间复杂度：
O(n^2)，s+=B[i][j];的执行次数为n^2。
int s=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) s+=B[i][j];
}
sum = s;
- 以下时间复杂度：
O(log₃n)
i = 1;
while(i<=n){
i=i*3;//执行次数f(n)。3^f(n)<=n。f(n) = log₃n。
}
- 以下时间复杂度：
O(√x)。
x=n;//n>1
y=0;
while(x>= (y+1)*(y+1))
y++;//执行次数f(n)。x>=(f(n)+1)²。f(n)=√x -1。忽略常数。
- 空间复杂度
算法的空间复杂度一般是指算法的辅助空间。
一位数组a[n]的空间复杂度：O(n)
二维数组a[n][m]的空间复杂度：O(n*m)
