【数据结构其实真不难】算法分析

【数据结构其实真不难】算法分析

前言

前面我们已经介绍了，研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相

同的需求，并且

也通过案例演示了不同算法之间时间耗费和空间耗费上的差异，但我们并不能将时间占用和空间占

用量化，因此，

接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。有关算法时间耗费分析，我们

称之为算法的时

间复杂度分析，有关算法的空间耗费分析，我们称之为算法的空间复杂度分析。

1.算法的时间复杂度分析

我们要计算算法时间耗费情况，首先我们得度量算法的执行时间，那么如何度量呢？

事后分析估算方法：

比较容易想到的方法就是我们把算法执行若干次，然后拿个计时器在旁边计时，这种事后统计的方

法看上去的确不

错，并且也并非要我们真的拿个计算器在旁边计算，因为计算机都提供了计时的功能。这种统计方

法主要是通过设

计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从

而确定算法效率

的高低，但是这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间

和精力，测试完

了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境

( 硬件环境 ) 的差别

导致测试的结果差异也很大。

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.算法采用的策略和方案；

2.编译产生的代码质量；

3. 问题的输入规模 ( 所谓的问题输入规模就是输入量的多少 ) ；

4. 机器执行指令的速度；

由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问

题的输入规模。

如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。

我么再次以之前的求和案例为例，进行分析。

需求：

计算 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 的差距。

为什么循环判断在算法 1 里执行了 n+1 次，看起来是个不小的数量，但是却可以忽略呢？我们来看

下一个例子：

需求：

计算 100 个 1+100 个 2+100 个 3+...100 个 100 的结果

代码：

public static void main(String[] args) { int sum=0; int n=100; for (int i = 1; i <=n ; i++) { for (int j = 1; j <=n ; j++) { sum+=i; } } System.out.println("sum="+sum); }

上面这个例子中，如果我们要精确的研究循环的条件执行了多少次，是一件很麻烦的事情，并且，

由于真正计算和

的代码是内循环的循环体，所以，在研究算法的效率时，我们只考虑核心代码的执行次数，这样可

以简化分析。

我们研究算法复杂度，侧重的是当输入规模不断增大时，算法的增长量的一个抽象 ( 规律 ) ，而不是

精确地定位需要

执行多少次，因为如果是这样的话，我们又得考虑回编译期优化等问题，容易主次跌倒。

我们不关心编写程序所用的语言是什么，也不关心这些程序将跑在什么样的计算机上，我们只关心

它所实现的算

程序的运行时间

时，最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行

时间，最重要的

就是把核心操作的次数和输入规模关联起来。

1.1函数渐近增长

概念：

给定两个函数 f(n) 和 g(n), 如果存在一个整数 N ，使得对于所有的 n>N,f(n) 总是比 g(n) 大，那么我们说

f(n) 的增长渐近

快于 g(n) 。

概念似乎有点艰涩难懂，那接下来我们做几个测试。

测试一：

假设四个算法的输入规模都是 n ：

1. 算法 A1 要做 2n+3 次操作，可以这么理解：先执行 n 次循环，执行完毕后，再有一个 n 次循环，最后有 3 次运算；

2.算法A2 要做 2n 次操作；

3. 算法 B1 要做 3n+1 次操作，可以这个理解：先执行 n 次循环，再执行一个 n 次循环，再执行一个 n 次

循环，最后有 1 次运算。

4.算法B2 要做 3n 次操作；

那么，上述算法，哪一个更快一些呢？

通过数据表格，比较算法 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 需要做 2n^2 次操作

4.算法D2 需要做 n^2 次操作

那么上述算法，哪个更快一些？

通过数据表格，对比算法 C1 和算法 D1 ：

当输入规模 n<=3 时，算法 C1 执行次数多于算法 D1 ，因此算法 C1 效率低一些；

当输入规模 n>3 时，算法 C1 执行次数少于算法 D1 ，因此，算法 D2 效率低一些，

所以，总体上，算法 C1 要优于算法 D1.

通过折线图，对比对比算法 C1 和 C2 ：

随着输入规模的增大，算法 C1 和算法 C2 几乎重叠

通过折线图，对比算法 C 系列和算法 D 系列：

随着输入规模的增大，即使去除 n^2 前面的常数因子， D 系列的次数要远远高于 C 系列。

因此，可以得出结论：

随着输入规模的增大，与最高次项相乘的常数可以忽略

测试三：

假设四个算法的输入规模都是 n ：

算法 E1:

2n^2+3n+1;

算法 E2 ：

n^2

算法 F1 ：

2n^3+3n+1

算法 F2 ：

n^3

那么上述算法，哪个更快一些？

通过数据表格，对比算法 E1 和算法 F1 ：

当 n=1 时，算法 E1 和算法 F1 的执行次数一样；

当 n>1 时，算法 E1 的执行次数远远小于算法 F1 的执行次数；

所以算法 E1 总体上是由于算法 F1 的。

通过折线图我们会看到，算法 F 系列随着 n 的增长会变得特块，算法 E 系列随着 n 的增长相比较算法 F

来说，变得比较

慢，所以可以得出结论：

最高次项的指数大的，随着 n 的增长，结果也会变得增长特别快

测试四：

假设五个算法的输入规模都是 n ：

算法 G ：

n^3;

算法 H:

n^2;

算法 I ：

n:

算法 J ：

logn

算法 K:

那么上述算法，哪个效率更高呢？

通过观察数据表格和折线图，很容易可以得出结论：

算法函数中 n 最高次幂越小，算法效率越高

总上所述，在我们比较算法随着输入规模的增长量时，可以有以下规则：

1. 算法函数中的常数可以忽略；

2. 算法函数中最高次幂的常数因子可以忽略；

3. 算法函数中最高次幂越小，算法效率越高。

1.2算法时间复杂度

1.2.1大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 表示法来表示一些求和算法的时间复杂度：

算法一：

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); }

算法二：

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); }

算法三：

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); }

如果忽略判断条件的执行次数和输出语句的执行次数，那么当输入规模为 n 时，以上算法执行的次

数分别为：

算法一： 3 次

算法二： n+3 次

算法三： n^2+2 次

如果用大 O 记法表示上述每个算法的时间复杂度，应该如何表示呢？基于我们对函数渐近增长的分

析，推导大 O 阶

的表示法有以下几个规则可以使用：

1. 用常数 1 取代运行时间中的所有加法常数；

2. 在修改后的运行次数中，只保留高阶项；

3. 如果最高阶项存在，且常数因子不为 1 ，则去除与这个项相乘的常数；

所以，上述算法的大 O 记法分别为：

算法一： O(1)

算法二： O(n)

算法三： O(n^2)

1.2.2常见的大O阶

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 次

2. 平方阶

一般嵌套循环属于这种时间复杂度

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(n^2).

3. 立方阶

一般三层嵌套循环属于这种时间复杂度

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(n^3).

4. 对数阶

对数，属于高中数学的内容，我们分析程序以程序为主，数学为辅，所以不用过分担心。

int i=1,n=100; while(i

由于每次 i*2 之后，就距离 n 更近一步，假设有 x 个 2 相乘后大于 n ，则会退出循环。由于是 2^x=n, 得

到 x=log(2)n, 所

以这个循环的时间复杂度为 O(logn);

对于对数阶，由于随着输入规模 n 的增大，不管底数为多少，他们的增长趋势是一样的，所以我们

会忽略底数。

5. 常数阶

一般不涉及循环操作的都是常数阶，因为它不会随着 n 的增长而增加操作次数。例如：

public static void main(String[] args) { int n=100; int i=n+2; System.out.println(i); }

上述代码，不管输入规模 n 是多少，都执行 2 次，根据大 O 推导法则，常数用 1 来替换，所以上述代

码的时间复杂度 为O(1)

下面是对常见时间复杂度的一个总结：

1.2.3函数调用的时间复杂度分析

之前，我们分析的都是单个函数内，算法代码的时间复杂度，接下来我们分析函数调用过程中时间

复杂度。

案例一：

public static void main(String[] args) { int n=100; for (int i = 0; i < n; i++) { show(i); } }private static void show(int i) { System.out.println(i); }}

在 main 方法中，有一个 for 循环，循环体调用了 show 方法，由于 show 方法内部只执行了一行代码，

所以 show 方法

的时间复杂度为 O(1), 那 main 方法的时间复杂度就是 O(n)

案例二：

public static void main(String[] args) { int n=100; for (int i = 0; i < n; i++) { show(i); } } private static void show(int i) { for (int j = 0; j < i; i++) { System.out.println(i); } }

在 main 方法中，有一个 for 循环，循环体调用了 show 方法，由于 show 方法内部也有一个 for 循环，

所以 show 方法

的时间复杂度为 O(n), 那 main 方法的时间复杂度为 O(n^2)

案例三：

public static void main(String[] args) { int n=100; show(n); for (int i = 0; i < n; i++) { show(i); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println(j); } } }private static void show(int i) { for (int j = 0; j < i; i++) { System.out.println(i); }}

在 show 方法中，有一个 for 循环，所以 show 方法的时间复杂度为 O(n), 在 main 方法中， show(n) 这行

代码内部执行

的次数为 n ，第一个 for 循环内调用了 show 方法，所以其执行次数为 n^2, 第二个嵌套 for 循环内只执行

了一行代码，

所以其执行次数为 n^2, 那么 main 方法总执行次数为 n+n^2+n^2=2n^2+n 。根据大 O 推导规则，去掉 n

保留最高阶

项，并去掉最高阶项的常数因子 2 ，所以最终 main 方法的时间复杂度为 O(n^2)

1.2.4最坏情况

从心理学角度讲，每个人对发生的事情都会有一个预期，比如看到半杯水，有人会说：哇哦，还有

半杯水哦！但也

有人会说：天哪，只有半杯水了。一般人处于一种对未来失败的担忧，而在预期的时候趋向做最坏

的打算，这样即

使最糟糕的结果出现，当事人也有了心理准备，比较容易接受结果。假如最糟糕的结果并没有出

现，当事人会很快 乐。

算法分析也是类似，假如有一个需求：

有一个存储了 n 个随机数字的数组，请从中查找出指定的数字。

public int search(int num){ int[] arr={11,10,8,9,7,22,23,0}; for (int i = 0; i < arr.length; i++) { if (num==arr[i]){ return i; } } return -1; }

最好情况：

查找的第一个数字就是期望的数字，那么算法的时间复杂度为 O(1)

最坏情况：

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

平均情况：

任何数字查找的平均成本是 O(n/2)

最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服

务，所以，除非

特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。

2.算法的空间复杂度分析

计算机的软硬件都经历了一个比较漫长的演变史，作为为运算提供环境的内存，更是如此，从早些

时候的 512k, 经

历了 1M ， 2M ， 4M... 等，发展到现在的 8G ，甚至 16G 和 32G ，所以早期，算法在运行过程中对内存

的占用情况也是 一个经常需要考虑的问题。我么可以用算法的空间复杂度来描述算法对内存的占用。

2.1java中常见内存占用

1. 基本数据类型内存占用情况：

2.计算机访问内存的方式都是一次一个字节

3. 一个引用（机器地址）需要 8 个字节表示：

例如： Date date = new Date(), 则 date 这个变量需要占用 8 个字节来表示

4. 创建一个对象，比如 new Date() ，除了 Date 对象内部存储的数据 ( 例如年月日等信息 ) 占用的内

存，该对象本身也

有内存开销，每个对象的自身开销是 16 个字节，用来保存对象的头信息。

5. 一般内存的使用，如果不够 8 个字节，都会被自动填充为 8 字节：

6.java 中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型

的数组一般需要

24 字节的头信息 (16 个自己的对象开销， 4 字节用于保存长度以及 4 个填充字节 ) 再加上保存值所需的

内存。

2.2算法的空间复杂度

了解了 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 开发的，基本上都是服务器开发，

一般不存在这样 的问题。

3.最后

我们的数据结构就结束了 欢迎大家添加博主交流 练习过程中遇到问题也可以提供支持 如果需要学习资料 博主也可以推荐

最后 如果觉得文章对您有帮助 请给博主点赞、收藏、关注 博主会不断推出更多优质文章

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。