1.算法分析

研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求，并且 也通过案例演示了不同算法之间时间耗费和空间耗费上的差异，但我们并不能将时间占用和空间占用量化，因此，接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。有关算法时间耗费分析，我们称之为算法的时间复杂度分析，有关算法的空间耗费分析，我们称之为算法的空间复杂度分析。

1.1算法的时间复杂度分析

①事后分析估算方法：

比较容易想到的方法就是我们把算法执行若干次，然后拿个计时器在旁边计时，这种事后统计的方法看上去的确不
错，并且也并非要我们真的拿个计算器在旁边计算，因为计算机都提供了计时的功能。这种统计方法主要是通过设
计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率
的高低，但是这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完
了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境(硬件环境)的差别
导致测试的结果差异也很大。

②事前分析估算方法：

在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机
上运行所消耗的时间取决于下列因素：
1.算法采用的策略和方案；
2.编译产生的代码质量；
3.问题的输入规模(所谓的问题输入规模就是输入量的多少)；
4.机器执行指令的速度；
由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。
如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。
总结：
1.算法函数中的常数可以忽略；
2.算法函数中最高次幂的常数因子可以忽略；
3.算法函数中最高次幂越小，算法效率越高。

算法时间复杂度

大O记法

定义：
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的
量级。算法的时间复杂度，就是算法的时间量度，记作:T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间
的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。
在这里，我们需要明确一个事情：执行次数=执行时间
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最
慢的算法为最优算法。

如果用大O记法表示上述每个算法的时间复杂度，应该如何表示呢？基于我们对函数渐近增长的分析，推导大O阶
的表示法有以下几个规则可以使用：
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数中，只保留高阶项；
3.如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；
image.png
他们的复杂程度从低到高依次为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)
从平方阶开始，随着输入规模的增大，时间成本会急剧增大，所以，我们的算法，尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度，而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的，那我们可以分为这种算法是不可取的，需要优化。

最坏情况

从心理学角度讲，每个人对发生的事情都会有一个预期，比如看到半杯水，有人会说：哇哦，还有半杯水哦！但也
有人会说：天哪，只有半杯水了。一般人处于一种对未来失败的担忧，而在预期的时候趋向做最坏的打算，这样即
使最糟糕的结果出现，当事人也有了心理准备，比较容易接受结果。假如最糟糕的结果并没有出现，当事人会很快
乐。
算法分析也是类似，假如有一个需求：
有一个存储了n个随机数字的数组，请从中查找出指定的数字。

最好情况：
查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
最坏情况：
查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
平均情况：
任何数字查找的平均成本是O(n/2)
最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非
特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。

1.2 算法的空间复杂度分析

计算机的软硬件都经历了一个比较漫长的演变史，作为为运算提供环境的内存，更是如此，从早些时候的512k,经
历了1M，2M，4M…等，发展到现在的8G，甚至16G和32G，所以早期，算法在运行过程中对内存的占用情况也是
一个经常需要考虑的问题。我么可以用算法的空间复杂度来描述算法对内存的占用。

1.2.1 java中常见内存占用

1.基本数据类型内存占用情况：
image.png
2.计算机访问内存的方式都是一次一个字节
image.png
3.一个引用（机器地址）需要8个字节表示：
例如： Date date = new Date(),则date这个变量需要占用8个字节来表示
4.创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也
有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。
5.一般内存的使用，如果不够8个字节，都会被自动填充为8字节：
image.png
6.java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要
24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

1.2.2 算法的空间的复杂度

eg：

  1. public static int[] reverse2(int[] arr){ 
  2.     int n=arr.length;//申请4个字节 
  3.     int[] temp=new int[n];//申请n*4个字节+数组自身头信息开销24个字节 
  4.     for (int i = n-1; i >=0; i--) { 
  5.         temp[n-1-i]=arr[i]; 
  6.     }
  7.     return temp; 
  8. }

由于java中有内存垃圾回收机制，并且jvm对程序的内存占用也有优化（例如即时编译），我们无法精确的评估一
个java程序的内存占用情况，但是了解了java的基本内存占用，使我们可以对java程序的内存占用情况进行估算。

由于现在的计算机设备内存一般都比较大，基本上个人计算机都是4G起步，大的可以达到32G，所以内存占用一般
情况下并不是我们算法的瓶颈，普通情况下直接说复杂度，默认为算法的时间复杂度。

但是，如果你做的程序是嵌入式开发，尤其是一些传感器设备上的内置程序，由于这些设备的内存很小，一般为几
kb，这个时候对算法的空间复杂度就有要求了，但是一般做java开发的，基本上都是服务器开发，一般不存在这样
的问题。