青海海东住房和城乡建设局网站,变性WordPress,服务器维护是什么意思,重庆的平台公司这里写目录标题 基本概念与术语数据数据元素数据项数据对象数据结构 逻辑结构和物理结构物理结构顺序存储结构链式存储结构 逻辑结构集合结构线性结构树形结构图形结构 算法时间复杂度和空间复杂度大O的渐进表示法时间复杂度常数阶线性阶对数阶平方阶常见时间复杂度 空间复杂度… 这里写目录标题 基本概念与术语数据数据元素数据项数据对象数据结构 逻辑结构和物理结构物理结构顺序存储结构链式存储结构 逻辑结构集合结构线性结构树形结构图形结构 算法时间复杂度和空间复杂度大O的渐进表示法时间复杂度常数阶线性阶对数阶平方阶常见时间复杂度 空间复杂度 最好情况与平均情况于最坏情况 基本概念与术语
概念皆来自于《大话数据结构》。
数据
数据的概念是描述客观事物的符号是计算机中可以操作的对象是能被计算机识别并输入给计算机处理的符号集合。 其实就是可以输入到计算机中可以被计算机处理的字符。像文件图像声音数字等等都是可以通过编码转换为字符来处理。
数据元素
数据元素的概念是组成数据的有一定意义的基本单位在计算机中通常作为整体处理也称为记录。
就像数学中由多个集合子集合构成的集合。子集就像数据元素一样
数据项
数据项概念一个数据元素可以由若干个数据项组成。 数据项就像集合中的元素。
数据对象
数据对象是性质相同的数据元素的集合是数据的子集。
关系 用∈代替一下‘包含于’关系 数据项∈数据元素∈数据对象∈数据
数据结构
数据结构概念:是互相之间存在一种或多种特定关系的数据元素的集合。
逻辑结构和物理结构
这是根据视点来区分的数据结构。
物理结构
物理结构是指数据的逻辑结构在计算机中的存储形式。
顺序存储结构
是把数据元素存放在地址连续的存储单元里其数据间的逻辑结构关系和物理结构关系是一致的。
链式存储结构
是把数据元素存放在任意位置的存储单元里这组存储单元可以是连续的也可以是不连续的。
逻辑结构
是指数据对象中数据元素之间的相互关系。
集合结构
集合结构中的数据元素除了同属于一个集合外他们之间没有其他关系。
线性结构
线性结构中的数据元素之间是一对一的关系。
树形结构
树形结构中的数据元素之间存在一种一对多的层次关系。
图形结构
图形结构中的数据元素是多对多的关系。
算法
算法的定义算法是解决特定问题求解步骤的描述在计算机中表现为指令的有限序列。并且每条指令表示一个或多个操作。 算法五大特性输入输出有穷性确定性可行性。
当多个算法都可以解决问题在保证了正确性、可读性、健壮性我们一般要考虑算法的时间效率空间效率。我们就要用时间复杂度和空间复杂度来衡量。
时间复杂度和空间复杂度
其实我们要求时间复杂度就把语句执行次数给加起来表示为一个函数空间复杂度开辟空间次数加起来表示为一个函数。然后将函数由大O的渐进表示法来表示。求得的就是复杂度。
我们通常使用大O的渐进表示法来表示时间复杂度和空间复杂度。
大O的渐进表示法
规则 1.用常数1来取代运行时间中的所有加法常数 2.在修改后的运行次数函数中只保留最高阶项 3.如果最高阶项存在且系数不为1则将系数修改为1。
时间复杂度
常数阶
int n 100;
int sum (n1)*n/2;这个高斯公式求和就是函数为3常数都表示为1大O渐进法时间复杂度表示就是O(1)。
线性阶
int n 100;
int sum 0;
for(int i 0; i n; i){sum i;
} 这个求和就是函数为n2保留最高阶大O渐进法时间复杂度表示就是O(n)。
对数阶
int count 1;
while(count n){count * 2;
}这个就是函数为logN1保留最高阶大O渐进法时间复杂度表示就是O(logN)。
平方阶
for(int i 0; i n; i){for(int j 0; j n; j){System.out.print(0 );}
}这个的函数为nn 1保留最高阶大O渐进法时间复杂度表示就是O(nn)。
常见时间复杂度
O(1) O(logN) O(N) O(NlogN) O(NN) O(2^N) O(N!) O(N*N)
空间复杂度
空间复杂度和时间复杂度求法完全一样只不过是将执行次数变为开辟空间次数。
int factorial(int N) {return N 2 ? N : factorial(N-1)*N;
}如上面代码每一次调用都要开辟一次递归了N次。空间复杂度就是O(N)。
最好情况与平均情况于最坏情况
最好情况就是当前要解决的问题完全契合当前算法。像写一个冒泡排序给的数组本身就是有序的此时直接返回值时间复杂度就是O(1)。
平均情况就是所有情况中最有意义的因为它是期望的运行时间。
最坏情况一般不说明我们像上面将诉的方法求的复杂度一般是最坏情况。
