一、数据结构
1.基本概念
1.1数据
程序的操作对象,用于描述客观事物.
1.2.数据的特点
- 可以输入到计算机
- 可以被计算机处理
1.3.数据项
一个数据元素由若干数据项组成
1.4.数据元素
组成数据的对象的基本单位
1.5.数据对象
性质相同的数据元素的集合(类似于数组)
1.6.结构
数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
1.7.数据结构
指的数据对象中的数据元素之间的关系
数据对象中的数据元素之间的关系
2.逻辑结构与物理结构
根据视角不同,我们将数据结构分为2种: 逻辑结构与物理结构;
2.1 逻辑结构
逻辑结构: 指的是数据对象中的数据元素之间的相互关系.具体采用什么的数据结构,是需要根据实际业务需求来进行合理的设计
逻辑结构又可以分为线性结构和非线性结构
线性结构: 线性结构中的数据元素之间是一对一的关系.
- 线性表
- 栈
- 队列
- 双队列
- 数组
- 串
非线性结构:数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。
- 集合结构
- 树形结构
- 图形结构
2.1.1 线性结构
线性结构
线性结构中的数据元素之间是一对一的关系
2.1.2 非线性结构
- 集合结构
集合结构
集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系. 各个数据元素是"平等"的. 它们的共同属性是:"同属于一个集合".
- 树形结构
树形结构
树形数据结构可以表示数据表树之间一对多的关系.树形结构中的数据元素之间存在一种一对多的层次关系. 常见的树形结构: 二叉树,B树,哈夫曼树,红黑树等.
-
图形结构
图形结构
图形结构的数据元素是多对多的关系. 常见的图形结构: 邻近矩阵,邻接表.
2.2 物理结构
物理结构,别称"存储结构". 顾名思义,指的是数据的逻辑结构在计算机的存储形式.
设计好逻辑数据结构之后,数据的存储也是非常重要的. 数据存储结构应该正确反映数据元素之间的逻辑关系.这才是关键! 如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点.
数据元素的存储结构形式有2种: 顺序存储和链式存储;
- 顺序存储结构
顺序存储结构
把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的.
- 链式存储结构
链式存储结构
把数据元素放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的. 数据元素的存储关系并不能反映逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关关联数据元素的位置.
3.抽象数据类型
3.1 数据类型
数据类型: 是指一组性质相同值的集合以及定义在此集合的一些操作的总称.
在C语言中,按照取值不同,数据类型可以分为2类:
- 原子类型: 是不可以在分解的基本数据类型,包含整型,浮点型,字符型等;
- 结构类型: 由若干类型组合而成,是可以再分解的.例如,整型数组就是由若干整型数据组成的.
3.2 抽象数据类型
抽象,是抽取出事物具有的普遍性的本质. 它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括. 抽象是一种思考问题的方式,它隐藏繁杂的细节,只保留实现目标所必需的信息.
抽象数据类型: 是指一个数学模型以及定义在该模型上的一组操作; 例如,我们在编写计算机绘图软件系统时,经常会使用到坐标. 也就是说,会经常使用x,y来描述横纵坐标. 而在3D系统中,Z深度就会出现. 既然这3个整型数字是始终出现在一起. 那就可以定义成一个Point的抽象数据类型. 它有x,y,z三个整型变量. 这样开发者就非常方便操作Point 数据变量.
抽象数据类型可以理解成实际开发里经常使用的结构体和类; 根据业务需求定义合适的数据类型以及动作.
二、算法
算法: 是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作.
2.1 算法与数据结构关系
算法与数据结构关系
算法是解决特定问题的求解步骤的描述; 而数据结构如果脱离算法,或者算法脱离数据结构都是无法进行的.
程序设计 = 数据结构 + 算法
2.2算法比较
实现程序: 求得1+2+3+......+100结果的程序?
int sum , n;
n = 100; sum = 0;
for(int i = 0; i <= n ; i++) {
sum += i;
}
printf(“%d”,sum);
但是，在18世纪德国的数学家高斯. 在小学时用数学的方式就解决了
int sum = 0 , n = 100;
sum = (1 + n) * n / 2;
printf(“%d”,sum);
对比以上2种方式,如果不仅仅是累积到100, 第一种方式,显然需要计算机循环1千次来模拟数学计算,而第二种方式肯定要比第一种来的快.
2.3算法的特性
算法必须具备几个基本特性: 输入,输出,有穷性,确定性和可行性;
- 输入输出
输入输出,很好理解. 在解决问题时必须有已知条件,当然有些算法可能没有输入. 但是算法至少有一个或多个输出.否则没有输出,没有结果.你用这个算法干吗?
- 有穷性
有穷性: 指的是算法在执行有限的步骤之后,自动结束而不会出现无限循环,且每一个步骤在可接受的时间内完成.
- 确定性
确定性: 算法的每一个步骤都具有确定的含义,不能出现二义性; 算法在一定条件下,只有一条执行路径,相同的输入只能有唯一的输出结果.
- 可行性
可行性: 算法的每一步都必须是可行的,换句话说,每一步都能通过执行有限次数完成.
2.4 算法设计要求
- 正确性
算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案;
正确分为4个层次:
(1).算法程序没有语法错误;
(2).算法程序对于合法的输入数据能够产生满足要求的输出结果;
(3).算法程序对于非法的输入数据能够得出满足规格说明的结果;
(4).算法程序对于精心选择的,甚至刁钻的测试数据都有满足要求的输出结果;
- 可读性
可读性: 算法设计的另一个目的是为了便于阅读,理解和交流; 可读性高有助于人们理解算法,晦涩难懂的算法往往隐含错误,且不容易发现并且难于调试和修改; 注意, 不要犯初学者的错误; 认为代码越少,就越牛逼! 可读性是算法好坏的很重要的标志!
- 健壮性
当输入数据不合法时,算法也能做出相关处理,而不是产生异常和莫名其妙的结果;
- 时间效率高和存储量低
生活中,人们希望花最少的钱,用最短的时间,办最大的事. 算法也是一样的思想. 用最少的存储空间,花最少的时间,办成同样的事.就是好算法!
2.5 算法时间复杂度
在进行算法分析时,语句的总执行次数T(n)是关于问题规模n的函数. 进而分析T(n)随着n变化情况并确定T(n)的数量级. 算法的时间复杂度,也就是算法的时间量度. T(n) = O(f(n)).
“它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。”
大写O( )来体现算法时间复杂度的记法，我们称之为大O表示法（大O记法）。
大O表示法规定
- 1.用常数1取代运行时间中所有加法常数
3+2+1 -> O(1); - 2.在修改后的运行次数函数中,只保留最高阶项
n^3+2n^2+5 -> O(n^3); - 3.如果在最高阶项存在且不是1,则去除与这个项相乘的常数
2n^3 -> n^3;
2.5.1 常数阶
//1+1+1 = 3
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum);//执行1次
}
这个算法的运行次数函数是f(n) = 3;根据我们大O时间复杂度表示为O(1);
//1+1+1+1+1+1+1 = 7
void testSum2(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum);//执行1次
}
事实上,无论常数n是多少.以上的代码执行3次还是7次的差异,执行时间恒定.我们的都称之为具有O(1)的时间复杂度.又称为"常数阶";
2.5.2 对数阶
int count = 1;
while(count < n){
count = count * 2;
}
count = count * 2 每次执行这句代码,就会距离n更近一步; 也就是说, 有多少个2相乘后大于n,则会退出循环. 所以,这个循环时间复杂度为: O(logn).
2.5.3 线性阶
线性阶的循环结构会复杂很多. 要确定某个算法的阶次,我们常常需要先确定某个特定语句或某个语句集的运行次数. 因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况.
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
这段代码的循环的时间复杂度为O(n).
2.5.4 平方阶
/x=x+1; 执行n*n次
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
循环次数为O(n^2)
//n+(n-1)+(n-2)+...+1 = n(n+1)/2 = n^2/2 + n/2
void testSum4(int n){
int sum = 0;
for(int i = 0; i < n;i++) //执行n次
for (int j = i; j < n; j++) { //执行n-i次
sum += j;
}
printf("textSum4:%d",sum);
}
由于当i = 0,内循环执行了n次. 当i=1时,执行n-1次,......
当i=n-1次,就执行1次;
所以总执行次数为:n+(n-1)+(n-2)+...+1 = n(n+1)/2 = (n^2)/2 + n/2
i = 0，循环执行次数是 n 次。
i = 1，循环执行次数是 n-1 次。
i = 2，循环执行次数是 n-2 次。
...
i = n-1，循环执行的次数是 1 次。
换算成:
result = n + (n - 1) + (n - 2) … + 1
被加数递减，抽象为一个等差数列求n项和的问题，公差为1，带入公式，Sn = n(a1 + an ) ÷2
result = (n(n+1))/2 = (n^2+n)/2 = (n^2)/2 + n/2
采用大O表示法
第一条,没有加法常数不予考虑;
第二条,只保留最高阶项,因此保留 (n^2) /2;
第三条,去除这个相乘的常数,也就是去除1/2. 最终的时间复杂度为O(n^2);
2.5.5 立方阶
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}
最终的时间复杂度为O(n^3)
2.5.6 常用的时间复杂度
常用的时间复杂度
指数阶O(2^n)和 阶乘阶 O(n!) 等除非是非常小的n值,否则哪怕n只有100,都会造成噩梦般的运行时间. 所以这种不切实际的算法时间复杂度,一般都不会考虑且讨论.
2.6 最坏情况与最好情况
最坏情况与最好情况
假设寻找 n = 6, 循环在第1次就可以找到它的位置!
假设寻找 n = 1, 循环在第10次就可以找到它的位置!
通常除非特别指定,我们提到的运行时间都是最坏情况下的运行时间.大O表示法也是最坏情况下的运行时间
2.7 算法空间复杂度
算法设计有一个重要原则，即空间/时间权衡原则（space/time tradeoff）。
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数.
程序空间计算因素:
1\. 寄存本身的指令
2\. 常数
3\. 变量
4\. 输入
5\. 对数据进行操作的辅助空间
在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间.
空间复杂度计算:
问题: 数组逆序,将一维数组a中的n个数逆序存放在原数组中.
int n = 10;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(1) ,仅仅通过借助一个临时变量temp,与问题规模n大小无关,所以其空间复杂度为O(1);
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
//算法实现(2) 借助一个大小为n的辅助数组b,所以其空间复杂度为O(n)
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
注意：算法的空间复杂度指的并不是整个算法在内存占用空间,而是指的是该算法在实现时所需要的辅助空间就可以
对一个算法,其时间复杂度和空间复杂度往往会互相影响. 当追求一个较好的时间空间复杂度时,可能会导致占用较多的存储空间. 即可能会使用空间复杂度的性能变差.反之亦然. 不过,通常情况下,鉴于运算空间较为充足,人们都以算法时间复杂度作为算法优先的衡量指标.
网友评论