整理的笔记
【有错请见谅且指出，无错以后自己看的时候有新见解再添】
- 资源
- 数据结构和算法概述
- 逻辑结构分类
- 物理结构分类
- 算法
- 算法分析
- 算法的时间复杂度分析
- 分析估算方法
- 函数渐近增长
- 大O记法
- 常见的大O阶
- 函数调用的时间复杂度分析
- 最坏情况
- 算法的空间复杂度分析
- Java中常见的内存占用
- 算法的空间复杂度
视频：https://www.bilibili.com/video/BV1iJ411E7xW
数据结构和算法
程序设计 = 数据结构 + 算法
数据结构和算法概述数据结构：是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。（就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据）
数据结构：逻辑结构（抽象意义）、物理结构（计算机内存上）
逻辑结构分类逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类。
a. 集合结构 集合结构中数据元素处理属于同一个集合外，他们之间没有任何其他的关系。
b. 线性结构 线性结构中的数据元素之间存在一对一的关系。
c. 树形结构 树形结构中的数据元素之间存在一对多的层次关系
d. 图形结构 图形结构的数据元素是多对多的关系
逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。
a. 顺序存储结构
把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如我们常用的数组就是顺序存储结构。
数组下标：0 1 2 3 … 8对应下图
好处：方便查找
坏处：插入、删除最坏情况需要移动全表
顺序存储结构存在一定的弊端，就像生活中排时也会有人插队也可能有人有特殊情况突然离开，这时候整个结构都处于变化中，此时就需要链式存储结构。
b. 链式存储结构
链式存储结构是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置
好处：插入、删除更快
坏处：插入、删除时的查找慢
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对—定规范的输入，在有限时间内获得所要求的输出。（根据一定的条件，对一些数据进行计算，得到需要的结果）
即解决方案
优秀的算法追求以下两个目标：
- 花最少的时间完成需求；
- 占用最少的内存空间完成需求；
算法最终目的：如何花更少的时间，如何占用更少的内存去完成相同的需求
时间复杂度分析：有关算法的时间耗费分析。
空间复杂度分析：有关算法的空间耗费分析。
算法的时间复杂度分析 分析估算方法事后分析估算方法：算法前 计时器，算法后 计时器。
缺陷︰必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境（硬件环境）的差别导致测试的结果差异也很大。
事前分析估算方法：在计算机程序编写前，依据统计方法对算法进行估算。
高级语言编写的程序，程序在计算机上运行所耗费的时间取决于下列因素：
- 算法采用的策略和方案；【使用哪个算法？】
- 编译产生的代码质量；【字节码文件质量如何？】
- 问题的输入规模（所谓的问题输入规模就是输入量的多少）；
- 机器执行指令的速度；
由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。
在研究算法的效率时，我们只考虑核心代码的执行次数。分析一个算法的运行时间，最重要的就是把核心操作的次数和输入规模关联起来。（核心操作的次数和输入规模的关联关系）
概念：给定两个函数fn)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)。
1. 随着输入规模的增大，算法的常数操作可以忽略不计
例： n n+1 实际上，加的常数随着输入规模的增大可以忽略不计。可以都看作是n
2. 随着输入规模的增大，与最高次项相乘的常数（系数）可以忽略
例： n2 3n2 实际上，系数和加的常数随着输入规模的增大可以忽略不计。可以都看作是n2
3. 最高次项的指数大的，随着n的增长，结果也会变得增长特别快（即只看最高次项的）
例： n2+n+5 n2 ====> n2
4. 算法函数中n最高次幂越小，算法效率越高
算法G∶n3
算法H：n2
算法l：n
算法J：log n
算法K：1
总结：
- 算法函数中的常数可以忽略
- 算法函数中最高次幂的常数因子可以忽略
- 算法函数中最高次幂越小，算法效率越高
定义：在进行算法分析时，语句总的执行次数Tn)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的量级。算法的时间复杂度，就是算法的时间量度，记作：T(n)=O(fin)。它表示随着问题规模n的增大，算法执行时间的增长率和fn)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。
执行次数 = 执行时间（？？？不太确定）
用大写 O() 来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。
基于对函数渐近增长的分析，推导大O阶的表示法有以下几个规则可以使用：【大O推导法则】
-
用常数1取代运行时间中的所有加法常数
例： 3 次 —> O(1)
-
在修改后的运行次数中，只保留高阶项
例：n+3 次 —> O(n)
-
如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数
例：n2+2 次 —> O(n2)
1. 线性阶
一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长。（一层循环，循环的时间复杂度为O(n)，因为循环体中的代码需要执行n次）
2. 平方阶
一般 两层嵌套循环属于这种时间复杂度。（例如双层循环，循环体中的代码需要执行内层循环次数x外层循环次数，时间复杂度为O(n2)）
3. 立方阶
一般为 三层嵌套循环。时间复杂度O(n3)
4. 对数阶乘
int i = 1,n = 100;
while(i < n) {
i = i * 2;
}
由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环。由于是2x=n（x次），得到x=log(2)n，所以这个循环的时间复杂度为O(log n)。
对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。重点在分析增长率
5. 常数阶
执行2次，执行10次，执行100次， —> O(1)
对常见时间复杂度的一个总结：
他们的复杂程度从低到高依次为：【时间复杂度越复杂，耗费的时间越多】
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)
【对于时间复杂度大于等于O(n2) ， O(n3)就要考虑优化代码】
函数调用的时间复杂度分析案例一：
案例二：
案例三：
对发生的事情有个预期。
最好情况︰查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
最坏情况∶查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
平均情况∶任何数字查找的平均成本是O(n/2)
最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。
【计算最坏情况下，程序的时间复杂度】
算法的空间复杂度分析 Java中常见的内存占用-
基本数据类型内存占用情况：
-
计算机访问内存的方式都是一次一个字节（1Byte= 8 Bit）
-
一个引用（机器地址）需要8个字节表示：
例如：Date date = new Date() //date这个变量需要占用8个字节来表示
-
创建一个对象，比如new Date()，除了Date对象内部存储的数据（例如年月日等信息）占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。
-
一般内存的使用，如果不够8个字节，都会被自动填充为8字节：
-
java中数组被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息（16个自己的对象开销，4字节用于保存长度以及4个填充字节）再加上保存值所需的内存。
算法的空间复杂度计算公式记作：S(n)=O(f(n))，其中n为输入规模，f(n)为语句关于n所占存储空间的函数。
案例：对指定的数组元素进行反转，并返回反转的内容。
解法一：
解法二：
忽略判断条件占用的内存，我们得出的内存占用情况如下：
算法一︰不管传入的数组大小为多少，始终额外申请4+4=8个字节；
算法二∶4+4n+24=4n+28;
根据大O推导法则，算法一的空间复杂度为o(1)，算法二的空间复杂度为o(n)。所以从空间占用的角度讲，算法一要优于算法二。
由于java中有内存垃圾回收机制，并且jvm对程序的内存占用也有优化（例如即时编译），我们无法精确的评估一个java程序的内存占用情况，但是了解了java的基本内存占用，使我们可以对java程序的内存占用情况进行估算。
由于现在的计算机设备内存一般都比较大，基本上个人计算机都是4G起步，大的可以达到32G，所以内存占用一般情况下并不是我们算法的瓶颈，普通情况下直接说复杂度，默认为算法的时间复杂度。
但是，如果你做的程序是嵌入式开发，尤其是一些传感器设备上的内置程序，由于这些设备的内存很小，一般为几kb，这个时候对算法的空间复杂度就有要求了，但是一般做java开发的，基本上都是服务器开发，一般不存在这样的问题。
