山东省环保厅官方网站建设项目,做快餐料包的网站有哪些,咨询行业网站开发,自己可以自己做公司的网站吗目录数据结构概述逻辑结构存储结构算法概述如何理解“大O记法”时间复杂度空间复杂度数据结构概述
数据结构可以简单的理解为数据与数据之间所存在的一些关系#xff0c;数据的结构分为数据的存储结构和数据的逻辑结构。 逻辑结构
集合结构#xff1a;数据元素同属于一个集…
目录数据结构概述逻辑结构存储结构算法概述如何理解“大O记法”时间复杂度空间复杂度数据结构概述
数据结构可以简单的理解为数据与数据之间所存在的一些关系数据的结构分为数据的存储结构和数据的逻辑结构。 逻辑结构
集合结构数据元素同属于一个集合他们之间是并列关系无其他的关系可以理解为中学时期学习的集合在一个范围之内有很多的元素元素间没有什么关系线性结构元素之间存在着一对一的关系可以理解为每个学生对应着一个学号学号与姓名就是线性结构树形结构元素之间存在着一对多的关系可以简单理解为家庭族谱一样一代接一代图形结构元素之间存在多对多的关系每一个元素可能对应着多个元素或被多个元素对应网状图
存储结构
顺序存储结构就是将数据进行连续的存储我们可以将它比喻成学校食堂打饭排队一样一个接着一个链式存储结构不是按照顺序存储的后一个进来的数只需要将他的地址告诉前一个节点前一个节点中就存放了它后面那个数的地址所以最后一个数的存储地址就是为null可以将这种结构比喻成商场吃饭叫号上面的号码比喻成是地址你可以之后后面的地址是什么上面的其他内容就是该节点的内容区别 顺序存储的特点是查询快插入或者删除慢链式存储的特点是查询慢插入或者删除快
算法概述
同一问题不同解决方法通过时间和空间复杂度判断算法的优劣算法没有最好的只有最合适的学习算法是为了积累学习思路掌握学习思路并不是为了解决某问题去记住某种算法对于时间复杂度与空间复杂度现在大多数开发情况下我们都在使用以空间换时间耗费更多的内存来保证拥有更快的速度。各排序算法复杂度及稳定性
如何理解“大O记法”
对于算法进行特别具体的细致分析虽然很好但在实践中的实际价值有限。对于算法的时间性质和空间性质最重要的是其数量级和趋势这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如可以认为 3n^2 和 100n^2 属于同一个量级如果两个算法处理同样规模实例的代价分别为这两个函数就认为它们的效率“差不多”都为n^2级。
时间复杂度
一个算法花费的时间与算法中语句的执行次数成正比例哪个算法中语句执行次数多,它花费时间就多。算法中的语句执行次数称为语句频度或时间频度,记为T(n)。n 称为问题的规模当 n 不断变化时时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此我们引入时间复杂度概念。
一般情况下算法中基本操作重复执行的次数是问题规模 n 的某个函数,用T(n)表示若有某个辅助函数f(n)使得当 n 趋近于无究大时T(n)/f(n)的极限值为不等于零的常数则称f(n)是T(n)的同数量级函数。记作T(n)O(f(n))称O(f(n))为算法的渐进时间复杂度简称时间复杂度。
有时候算法中基本操作重复执行的次数还随问题的输入数据集不同而不同,如在冒泡排序中输入数据有序而无序结果是不一样的。此时我们计算平均值。
时间复杂度基本计算规则
基本操作即只有常数项认为其时间复杂度为O(1)顺序结构时间复杂度按加法进行计算循环结构时间复杂度按乘法进行计算分支结构时间复杂度取最大值判断一个算法的效率时往往只需要关注操作数量的最高次项其它次要项和常数项可以忽略在没有特殊说明时我们所分析的算法的时间复杂度都是指最坏时间复杂度
常用时间复杂度
注意经常将log2n以2为底的对数简写成logn
常见时间复杂度之间的关系 所以时间消耗由小到大为O(1) O(log n) O(n) O(nlog n) O(n^2) O(2^n) O(n!) O(n^n)
案例1
count 0; (1)for(i 0;i n;i) (2)for(j 0;j n;j) (3)count; (4)语句1执行1次语句2执行n次语句3执行n^2次语句4执行n^2次时间复杂度为T(n) 1nn^2n^2 O(n^2)
案例2
a 1; (1)
b 2; (2)
for(int i 1;i n;i) { (3)int s a b; (4)b a; (5)a s; (6)
} 语句1、2执行1次语句3执行n次语句4、5、6执行n次时间复杂度为T(n) 114n o(n)
案例3
i 1; (1)
while(in) {i i*2; (2)
} 语句1的频度是1设语句2的频度是f(n)则2f(n)n;f(n)log2n,取最大值f(n) log2n时间复杂度为T(n) O(log2n)
空间复杂度 算法的空间复杂度计算公式S(n) 0( f(n) )其中 n 为输入规模f(n)为语句关于 n 所占存储空间的函数 一个算法在计算机存储器上所占用的存储空间包括三个方面 存储算法本身所占用的存储空间算法的输入输出数据所占用的存储空间算法在运行过程中临时占用的存储空间
案例指定的数组进行反转并返回反转的内容
解法一
public static int[] reverse1(int[] arr) {int n arr.length; //申请4个字节int temp; //申请4个字节for (int start 0, end n - 1; start end; start, end--) {temp arr[start];arr[start] arr[end];arr[end] temp;}return arr;
}空间复杂度为S(n) 44 O(8) O(1)
解法二
public static int[] reverse2(int[] arr) {int n arr.length; //申请4个字节int[] temp new int[n]; //申请n*4个字节数组自身头信息开销24个字节for (int i n - 1; i 0; i--) {temp[n - 1 - i] arr[i];}return temp;
}空间复杂度为S(n) 44n24 O(n28) O(n)
根据大O推导法则算法一的空间复杂度为0(1),算法二的空间复杂度为0(n)所以从空间占用的角度讲算法一要优于算法二。
由于java中有内存垃圾回收机制并且jvm对程序的内存占用也有优化(例如即时编译) , 我们无法精确的评估一个java程序的内存占用情况但是了解了java的基本内存占用使我们可以对java程序的内存占用情况进行估算。
由于现在的计算机设备内存一般都比较大基本上个人计算机都是4G起步大的可以达到32G 所以内存占用一般情况下并不是我们算法的瓶颈普通情况下直接说复杂度默认为算法的时间复杂度。
但是如果你做的程序是嵌入式开发尤其是一些传感器设备上的内置程序,由于这些设备的内存很小, 一般为几kb这个时候对算法的空间复杂度就有要求了但是一般做java开发的基本上都是服务器开发, 一般不存在这样的问题。
