算法基础

 
研究算法的最终目的就是如何花更少的时间,如何占用更少的内存去完成相同的需求。
有关算法时间耗费分析,我们称之为算法的时间复杂度分析,有关算法的空间耗费分析,我们称之为算法的空间复杂度分析。

算法定义

 
算法是根据一定的条件,对一些数据进行计算,得到需要的结果的方法。在程序中,我们可以使用不同的算法来解决相同的问题,而不同的算法的成本也是不同的。
一个优秀的算法追求以最短的时间和以最少的内存空间完成需求的目标。

时间复杂度分析

度量算法执行时间的方式

事后分析估算方法

通过设计好的测试程序和测试数据,利用计算机计时器对不同的算法编制的程序的运行时间进行比较,从而确定算法效率的高低,但是这种方法有很大的缺陷:必须依据算法实现编制好的测试程序,通常要花费大量时间和精力,测试完了如果发现测试的是非常糟糕的算法,那么之前所做的事情就全部白费了,并且不同的测试环境(硬件环境)的差别导致测试的结果差异也很大。
public static void main(String[] args) { long start = System.currentTimeMillis(); int sum = 0; int n=100; for (int i = 1; i <= n; i++) { sum += i; } System.out.println("sum=" + sum); long end = System.currentTimeMillis(); System.out.println(end-start); }

事前分析估算方法

在计算机程序编写前,依据统计方法对算法进行估算,经过总结,我们发现一个高级语言编写的程序程序在计算机
上运行所消耗的时间取决于下列因素:
  1. 算法采用的策略和方案;
  1. 编译产生的代码质量;
  1. 问题的输入规模(所谓的问题输入规模就是输入量的多少);
  1. 机器执行指令的速度;
 
案例1 : 计算1到100的和。
第一种解法
如果输入量为n为1,则需要计算1次; 如果输入量n为1亿,则需要计算1亿次; public static void main(String[] args) { int sum = 0;//执行1次 int n=100;//执行1次 for (int i = 1; i <= n; i++) {//执行了n+1次 sum += i;//执行了n次 } System.out.println("sum=" + sum); }
第二种解法
如果输入量为n为1,则需要计算1次; 如果输入量n为1亿,则需要计算1次; public static void main(String[] args) { int sum = 0;//执行1次 int n=100;//执行1次 sum = (n+1)*n/2;//执行1次 System.out.println("sum="+sum); }
因此,当输入规模为n时,第一种算法执行了1+1+(n+1)+n=2n+3次;第二种算法执行了1+1+1=3次。如果我们把 第一种算法的循环体看做是一个整体,忽略结束条件的判断,那么其实这两个算法运行时间的差距就是n和1的差 距。
忽略循环条件执行次数的原因
我们要精确的研究循环的条件执行了多少次,是一件很麻烦的事情,并且,由于真正计算和的代码是循环体,所以,在研究算法的效率时,我们只考虑核心代码的执行次数,这样可以简化分析。
我们分析一个算法的运行时间,最重要的就是把核心操作的次数输入规模关联起来。
notion image

算法比较的基本规则

给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么我们说f(n)的增长渐近 快于g(n)。
在我们比较算法随着输入规模的增长量时,可以有以下规则:
  1. 算法函数中的常数可以忽略
  1. 算法函数中最高次幂的常数因子可以忽略
  1. 算法函数中最高次幂越小,算法效率越高。
 
测试一: 假设四个算法的输入规模都是n: 1.算法A1要做2n+3次操作,可以这么理解:先执行n次循环,执行完毕后,再有一个n次循环,最后有3次运算; 2.算法A2要做2n次操作; 3.算法B1要做3n+1次操作,可以这个理解:先执行n次循环,再执行一个n次循环,再执行一个n次循环,最后有1 次运算。 4.算法B2要做3n次操作; 那么,上述算法,哪一个更快一些呢?
notion image
notion image
通过数据表格,比较算法A1和算法B1: 当输入规模n=1时,A1需要执行5次,B1需要执行4次,所以A1的效率比B1的效率低; 当输入规模n=2时,A1需要执行7次,B1需要执行7次,所以A1的效率和B1的效率一样; 当输入规模n>2时,A1需要的执行次数一直比B1需要执行的次数少,所以A1的效率比B1的效率高
所以我们可以得出结论:
当输入规模n>2时,算法A1的渐近增长小于算法B1 的渐近增长
通过观察折线图,我们发现,随着输入规模的增大,算法A1和算法A2逐渐重叠到一块,算法B1和算法B2逐渐重叠 到一块,所以我们得出结论: 随着输入规模的增大,算法的常数操作可以忽略不计
 
测试二: 假设四个算法的输入规模都是n: 1.算法C1需要做4n+8次操作 2.算法C2需要做n次操作 3.算法D1需要做次操作 4.算法D2需要做次操作 那么上述算法,哪个更快一些?
notion image
notion image
通过数据表格,对比算法C1和算法D1: 当输入规模n<=3时,算法C1执行次数多于算法D1,因此算法C1效率低一些; 当输入规模n>3时,算法C1执行次数少于算法D1,因此,算法D2效率低一些, 所以,总体上,算法C1要优于算法D1.
通过折线图,对比对比算法C1和C2: 随着输入规模的增大,算法C1和算法C2几乎重叠 通过折线图,对比算法C系列和算法D系列: 随着输入规模的增大,即使去除前面的常数因子,D系列的次数要远远高于C系列。
因此,可以得出结论: 随着输入规模的增大,与最高次项相乘的常数可以忽略
 
测试三: 假设四个算法的输入规模都是n: 算法E1: 算法E2: 算法F1: 算法F2: 那么上述算法,哪个更快一些?
notion image
notion image
通过数据表格,对比算法E1和算法F1: 当n=1时,算法E1和算法F1的执行次数一样; 当n>1时,算法E1的执行次数远远小于算法F1的执行次数; 所以算法E1总体上是由于算法F1的。 通过折线图我们会看到,算法F系列随着n的增长会变得特块,算法E系列随着n的增长相比较算法F来说,变得比较 慢,所以可以得出结论: 最高次项的指数大的,随着n的增长,结果也会变得增长特别快
 
测试四: 假设五个算法的输入规模都是n: 算法G:; 算法H: ; 算法I:n: 算法J: 算法K:1
那么上述算法,哪个效率更高呢?
notion image
notion image
通过观察数据表格和折线图,很容易可以得出结论:
算法函数中n最高次幂越小,算法效率越高
 

大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阶的表示法有以下几个规则可以使用:
  1. 用常数1取代运行时间中的所有加法常数;
  1. 在修改后的运行次数中,只保留高阶项;
  1. 如果最高阶项存在,且常数因子不为1,则去除与这个项相乘的常数;
下面我们使用大O表示法来表示一些求和算法的时间复杂度:
复杂度O(1)
如果输入量为n为1,则需要计算1次; 如果输入量n为1亿,则需要计算1亿次; public static void main(String[] args) { int sum = 0;//执行1次 int n=100;//执行1次 for (int i = 1; i <= n; i++) { sum += i;//执行了n次 } System.out.println("sum=" + sum); }
O(1)
如果输入量为n为1,则需要计算1次; 如果输入量n为1亿,则需要计算1次; public static void main(String[] args) { int sum = 0;//执行1次 int n=100;//执行1次 sum = (n+1)*n/2;//执行1次 System.out.println("sum="+sum); }
O(n)
public static void main(String[] args) { int sum=0;//执行1次 int n=100;//执行1次 for (int i = 1; i <=n ; i++) { for (int j = 1; j <=n ; j++) { sum+=i;//执行n^2次 } } System.out.println("sum="+sum); }
 

常见的大O阶

  1. 线性阶
    1. 一般含有非嵌套循环涉及线性阶,线性阶就是随着输入规模的扩大,对应计算次数呈直线增长,例如:
      public static void main(String[] args) { int sum = 0; int n=100; for (int i = 1; i <= n; i++) { sum += i; } System.out.println("sum=" + sum); }
      它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次。
  1. 平方阶
    1. 一般嵌套循环属于这种时间复杂度
      public static void main(String[] args) { int sum=0,n=100; for (int i = 1; i <=n ; i++) { for (int j = 1; j <=n ; j++) { sum+=i; } } System.out.println(sum); }
      上面这段代码,n=100,也就是说,外层循环每执行一次,内层循环就执行100次,那总共程序想要从这两个循环 中出来,就需要执行100*100次,也就是n的平方次,所以这段代码的时间复杂度是O().
  1. 立方阶
    1. 一般三层嵌套循环属于这种时间复杂度
      public static void main(String[] args) { int x=0,n=100; for (int i = 1; i <=n ; i++) { for (int j = i; j <=n ; j++) { for (int j = i; j <=n ; j++) { x++; } } } System.out.println(x); }
      上面这段代码,n=100,也就是说,外层循环每执行一次,中间循环循环就执行100次,中间循环每执行一次,最 内层循环需要执行100次,那总共程序想要从这三个循环中出来,就需要执行100*100*100次,也就是n的立方,所 以这段代码的时间复杂度是O().
  1. 对数阶
    1. int i=1,n=100; while(i<n){ i = i*2; }
      由于每次i*2之后,就距离n更近一步,假设有x个2相乘后大于n,则会退出循环。由于是=n,得到,所 以这个循环的时间复杂度为O(logn); 对于对数阶,由于随着输入规模n的增大,不管底数为多少,他们的增长趋势是一样的,所以我们会忽略底数。
      notion image
      notion image
  1. 常数阶
    1. 一般不涉及循环操作的都是常数阶,因为它不会随着n的增长而增加操作次数。例如:
      public static void main(String[] args) { int n=100; int i=n+2; System.out.println(i); }
      上述代码,不管输入规模n是多少,都执行2次,根据大O推导法则,常数用1来替换,所以上述代码的时间复杂度为O(1)
 
下面是对常见时间复杂度的一个总结:
notion image
他们的复杂程度从低到高依次为: O(1)<O(logn)<O(n)<O(nlogn)<O()<O() 根据前面的折线图分析,我们会发现,从平方阶开始,随着输入规模的增大,时间成本会急剧增大,所以,我们的算法,尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度,而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的,那我们可以分为这种算法是不可取的,需要优化。
 

最好,最坏,平均时间复杂度

一般人处于一种对未来失败的担忧,而在预期的时候趋向做最坏的打算,这样即使最糟糕的结果出现,当事人也有了心理准备,比较容易接受结果。假如最糟糕的结果并没有出现,当事人会很快乐。 算法分析也是类似,假如有一个需求: 在一个无序的数组(array)中,查找变量 x 出现的位置。如果没有找到,就返回 -1。
// n 表示数组 array 的长度 int find(int[] array, int n, int x) { int i = 0; int pos = -1; for (; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; }

最好情况时间复杂度

在最理想的情况下,查找的第一个数字就是期望的数字,那么算法的时间复杂度为O(1)

最坏情况时间复杂度

查找的最后一个数字,才是期望的数字,那么算法的时间复杂度为O(n)

平均时间复杂度

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度,发生的概率其实并不大。为了更好地表示平均情况下的复杂度,我们需要引入另一个概念:平均情况时间复杂度,简称为平均时间复杂度。
要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值,即:
notion image
我们知道,时间复杂度的大 O 标记法中,可以省略掉系数、低阶、常量,所以这个公式简化之后,得到的平均时间复杂度就是 O(n)。

加权平均值

前面的推导过程中存在的最大问题就是,没有将各种情况发生的概率考虑进去。
要查找的变量 x,要么在数组里,要么就不在数组里。这两种情况对应的概率统计起来很麻烦,为了方便理解,我们假设在数组中与不在数组中的概率都为 1/2。另外,要查找的数据出现在 0~n-1 这 n 个位置的概率也是一样的,为 1/n。所以,根据概率乘法法则,要查找的数据出现在 0~n-1 中任意位置的概率就是 1/(2n)。
那平均时间复杂度的计算过程就变成了这样
notion image
这个值就是概率论中的加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度
引入概率之后,前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示,去掉系数和常量,这段代码的加权平均时间复杂度仍然是 O(n)。
 

均摊时间复杂度

// array 表示一个长度为 n 的数组 // 代码中的 array.length 就等于 n int[] array = new int[n]; int count = 0; void insert(int val) { if (count == array.length) { int sum = 0; for (int i = 0; i < array.length; ++i) { sum = sum + array[i]; } array[0] = sum; count = 1; } array[count] = val; ++count; }
最理想的情况下,数组中有空闲空间,我们只需要将数据插入到数组下标为 count 的位置就可以了,所以最好情况时间复杂度为 O(1)。最坏的情况下,数组中没有空闲空间了,我们需要先做一次数组的遍历求和,然后再将数据插入,所以最坏情况时间复杂度为 O(n)。
那平均时间复杂度是多少呢?答案是 O(1)。
假设数组的长度是 n,根据数据插入的位置的不同,我们可以分为 n 种情况,每种情况的时间复杂度是 O(1)。除此之外,还有一种“额外”的情况,就是在数组没有空闲空间时插入一个数据,这个时候的时间复杂度是 O(n)。而且,这 n+1 种情况发生的概率一样,都是 1/(n+1)。所以,根据加权平均的计算方法,我们求得的平均时间复杂度就是:
notion image
 
  1. insert() 在大部分情况下,时间复杂度都为 O(1)。只有个别情况下,复杂度才比较高,为 O(n)
  1. 对于 insert() 函数来说,O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入,出现的频率是非常有规律的,而且有一定的前后时序关系,一般都是一个 O(n) 插入之后,紧跟着 n-1 个 O(1) 的插入操作,循环往复。
所以,针对这样一种特殊场景的复杂度分析,我们并不需要像之前讲平均复杂度分析方法那样,找出所有的输入情况及相应的发生概率,然后再计算加权平均值。
针对这种特殊的场景,我们引入了一种更加简单的分析方法:摊还分析法,通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度
每一次 O(n) 的插入操作,都会跟着 n-1 次 O(1) 的插入操作,所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。
 

空间复杂度分析

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

java中常见内存占用

  1. 基本数据类型内存占用情况:
    1. notion image
  1. 计算机访问内存的方式都是一次一个字节
    1. notion image
  1. 一个引用(机器地址)需要8个字节表示:
    1. 例如: Date date = new Date(),则date这个变量需要占用8个字节来表示
  1. 创建一个对象,比如new Date(),除了Date对象内部存储的数据(例如年月日等信息)占用的内存,该对象本身也有内存开销,每个对象的自身开销是16个字节,用来保存对象的头信息。
  1. 一般内存的使用,如果不够8个字节,都会被自动填充为8字节:
    1. notion image
  1. java中数组被被限定为对象,他们一般都会因为记录长度而需要额外的内存,一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销,4字节用于保存长度以及4个填充字节)再加上保存值所需的内存
了解了java的内存最基本的机制,就能够有效帮助我们估计大量程序的内存使用情况。 算法的空间复杂度计算公式记作:S(n)=O(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; }
解法二:
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; }
忽略判断条件占用的内存,我们得出的内存占用情况如下: 算法一: 不管传入的数组大小为多少,始终额外申请4+4=8个字节; 算法二: 4+4n+24=4n+28; 根据大O推导法则,算法一的空间复杂度为O(1),算法二的空间复杂度为O(n),因此从空间占用的角度来看,算法一优于算法二。
由于Java具有内存垃圾回收机制,而且JVM对程序的内存占用也有优化(例如即时编译),我们无法精确评估Java程序的内存占用情况。但是了解Java的基本内存占用情况,可以使我们对Java程序的内存占用情况进行估算。
由于现在计算机设备内存一般都比较大,基本上个人计算机都是4G起步,大的可以达到32G,因此内存占用一般情况下并不是我们算法的瓶颈。普通情况下,默认为算法的时间复杂度。
但是,如果你做的程序是嵌入式开发,尤其是一些传感器设备上的内置程序,由于这些设备的内存很小,一般只有几KB,这个时候对算法的空间复杂度就有要求了。但是一般做Java开发的,基本上都是服务器开发,一般不存在这样的问题。
 

算法技巧

算法技巧