数据结构与算法01——基础概念
一、数据结构的概述
数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
数据结构中有五个基本的概念：数据，数据元素，数据项，数据对象，数据结构。
1.1 数据：
image.png
数据（Data）是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
1.2 数据元素：
数据元素（data element）是组成数据的基本单位,在计算机中通常作为整体处理，也被称作"记录"。
1.3 数据项：
数据项（data item）一个数据元素可以由若干数据项组成，数据项是数据不可分割的最小单位。
1.4 数据对象：
数据对象（data object）是性质相同的数据元素的集合，是数据的子集。
1.5 数据结构：
数据结构（data structure）简单理解就是关系。不同数据元素之间并非独立而是存在特定的关系，我们将这些关系成为结构。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
二、逻辑结构和物理结构
数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。
2.1 数据的逻辑结构：
逻辑结构（logical structure） 指反应数据元素之间的逻辑关系的数据结构，其中的逻辑结构是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。逻辑结构包括：
2.1.1 集合：
数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
image.png
2.1.2 线性结构：
数据结构中的元素存在一对一的相互关系；（例如：线性表，栈，队列等）
image.png
2.1.3 树形结构：
数据结构中的元素存在一对多的相互关系；（例如：二叉树，哈夫曼树等）
image.png
2.1.4 图形结构：
数据结构中的元素存在多对多的相互关系。（例如：邻接矩阵）
image.png
2.2 数据的物理结构：
数据的逻辑结构在计算机中的存储形式
2.2.1 顺序存储结构：
数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。
image.png
**2.2.2 链式存储结构: **
数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
image.png
三、算法特性
有穷行： 算法可以在某一个条件下自动结束而不是出现无限循环。
确定性： 算法执行的每一步骤在一定条件下只有一条执行路径，一个相同的输入对应相同的一个输出。
可行性： 算法每一步骤都必须可行，能够通过有限的执行次数完成
输入： 算法具有零个或多个输入
输出： 算法至少有一个或多个输出
四、算法效率衡量方法：
正确性
可读性
健壮性
高效性
五、算法时间复杂度:大O表示法
用常数1取代运行时间中所有常数 3->1 O(1)
在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
六、常见的算法复杂度
6.1 常数阶：
//1常数阶 执行3次O(1)
void testNum1( int n){
int sum=0; //执行一次
sum=(n+1)*n/2; //执行一次
printf( "sum=%d\n",sum ); //执行一次
}
6.2 线性阶：
//x=x+1; 执行n次 O(n)
void add2 (int x, int n){
for( int i=0; i<n; i++ ){ //执行n次
x=x+1;
}
}
6.3 平方阶：
//x=x+1; 执行n*n次 ->O(n^2)
void add3 (int x ,int n ){
for( int i=0; i<n; i++ ){ //执行n次
for( int j=0; j<n; j++){ //执行n次
x=x+1;
}
}
}
6.4 对数阶：
/* 2的x次方等于n x = log2n ->O( log n)*/
void test4( int n ){
int count=1;//执行1次 //n = 10
while ( count<n ){
count = count*2;
}
}
6.5 立方阶：
void test5(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次
}
}
}
}
6.6 nlog阶
6.7 指数阶
image.png
指算法需要的计算工作量，通常我们所遇见的时间复杂度包括：
其中：O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
6.8 空间复杂度：
算法的空间复杂度是指算法需要消耗的内存空间
通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数
