数据结构与算法01-概念
Created At :
Count:1.1k
Views 👀 :
数据结构与算法
第一讲
##1.1 什么是数据结构
- 官方统一定义—— 没有……
- “数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”
- Sartaj Sahni，《数据结构、算法与应用》“数据结构是ADT（抽象数据类型 Abstract DataType）的物理实现。”
- Clifford A.Shaffer，《数据结构与算法分析》“数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。”
例题：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。
解决问题方法的效率，跟空间的利用效率有关。
所以到底什么是数据结构？？？
数据对象在计算机中的组织方式
- 逻辑结构
- 物理存储结构
- 数据对象必定与一系列加在其上的操作相关联
- 完成这些操作所用的方法就是算法
抽象数据类型（Abstract Data Type）
- 数据类型
- 数据对象集
- 数据集合相关联的操作集
- 抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集，“是什么”，并不涉及“如何做到”的问题。
1.2 什么是算法
算法（Algorithm）
- 一个有限指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能处理的范围之内
- 描述应不依赖于任何一种计算机语言以及具体的实现手段
例1：选择排序算法的伪码描述
1
2
3
4
5
6
7
8
9
10
11
12
|
void SelectionSort ( int List[], int N )
{
for ( i = 0; i < N; i ++ ) {
MinPosition = ScanForMin( List, i, N–1 );
Swap( List[i], List[MinPosition] );
}
}
|
什么是好的算法？
- 空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
- 时间复杂度T(n)—— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
在分析一般算法的效率时，我们经常关注下面两种复杂度
1.3 最大子列和问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| int Max3( int A, int B, int C )
{
return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer( int List[], int left, int right )
{
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int center, i;
if( left == right ) {
if( List[left] > 0 ) return List[left];
else return 0;
}
center = ( left + right ) / 2;
MaxLeftSum = DivideAndConquer( List, left, center );
MaxRightSum = DivideAndConquer( List, center+1, right );
MaxLeftBorderSum = 0; LeftBorderSum = 0;
for( i=center; i>=left; i-- ) {
LeftBorderSum += List[i];
if( LeftBorderSum > MaxLeftBorderSum )
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0; RightBorderSum = 0;
for( i=center+1; i<=right; i++ ) {
RightBorderSum += List[i];
if( RightBorderSum > MaxRightBorderSum )
MaxRightBorderSum = RightBorderSum;
}
return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
int MaxSubseqSum3( int List[], int N )
{
return DivideAndConquer( List, 0, N-1 );
}
|
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1210331079@qq.com
