logo头像
Snippet 博客主题

【数据结构与算法】数据结构与算法初识

1. 学前介绍

1.1 学习理由

你是不是觉得数据结构和算法,跟操作系统、计算机网络一样,是脱离实际工作的知识?可能除了面试,这辈子也用不着?

数据结构和算法这门课程无论在哪个学校的计算机相关专业,都是一门必修课 。包括我本人在内,在大学所学的数据结构知识都是略知皮毛,工作后才知道这门课程非常重要的,是编程必备的基础。因此,我从我自身找出了几个不想学或学不好数据结构与算法的常见原因:

  • 这门课程逻辑性强大,学习枯燥,不太好学,自然学不好。
  • 工作中用不到数据结构算法,可以用封装好的框架和API解决工作难题,觉得不需要重复造轮子,学不学无所谓,得过且过。
  • 没时间学习,时间管理能力太差,懒得学习,要我干什么都行(吃喝玩乐),反正不学习就行。
  • 内心太浮躁、太安逸,沉不下心,只享受此时的安逸,却不知未来的恐惧。

我相信大多数朋友也和我一样,以如此的状态进行生活、工作。但是渐渐的发现,无论通过任何方式都无法掩盖我内心的恐惧。处于一线城市的我,除了迷茫还是迷茫……

于是又过一段时间,开始慢慢调整,规划自己的知识体系,开始频繁学习知识、更新博客,补齐自己的短板,实现自我价值。

只要心中还有梦,任何时候的开始,都为时不晚。

每一个不曾起舞的日子,都是对生命的辜负。

经过反思,我对这门课程有了更深刻的认知:

  • 程序设计 = 数据结构 + 算法,恒古不变的基本功。
  • 想要通关大厂面试,千万别让数据结构和算法拖了后腿。
  • 不想写一辈子的CRUD,高质量的代码需要数据结构和算法。
  • 阅读优秀源码时,到处都是数据结构、算法、设计模式的缩影,要想读的懂源码,理解透彻其背后的设计思想,就需要数据结构和算法。
  • 训练大脑的思考能力,让大脑的逻辑性更加缜密,防止老年痴呆,学到老,活到老。

1.2 学习内容

最常用的、最基础的十种数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。

最常用的十种算法:递归算法、排序算法、二分查找、搜索算法、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

数据结构与算法学习路线

1.3 学习技巧

  • 边学边练,举一反三,适度刷题
  • 欲速则不达,多思考、多互动、多总结。
  • 反复迭代,不断沉淀,突破自我。
  • 坚持坚持再坚持,请记得每天一小时学习与训练。

2. 数据结构与算法

2.1 数据结构

2.1.1 数据结构定义

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

简单来说,数据结构是计算机存储、组织数据的方式。是把数据元素按照一定的关系组织起来的集合。

2.1.2 数据结构分类

2.1.2.1 逻辑结构

逻辑结构是从具体问题中抽象出来的模型,是抽象意义上的结构,按照对象中数据元素之间的相互关系分类,也是我们需要关注和讨论的问题。

  • 集合结构:集合结构中数据元素除了属于同一个集合外,他们之间没有任何其他的关系。

    image-20200804101325212

  • 线性结构:线性结构中的数据元素之间存在一对一的关系。

    image-20200804101512179

  • 树形结构:树形结构中的数据元素之间存在一对多的层次关系。

    image-20200804101642354

  • 图形结构:图形结构的数据元素是多对多的关系。

    image-20200804101824307

2.1.2.2 物理结构

逻辑结构在计算机中真正的表示方式(又称为映像)称为物理结构,也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。

  • 顺序存储结构
    ​ 把数据元素放到地址连续的存储单元里面,其数据间的逻辑关系和物理关系是一致的 ,比如我们常用的数组就是顺序存储结构。

    ​ 顺序存储结构存在一定的弊端,就像生活中排时也会有人插队也可能有人有特殊情况突然离开,这时候整个结构都处于变化中,此时就需要链式存储结构。

    image-20200804102645011

  • 链式存储结构

    是把数据元素存放在任意的存储单元里面,这组存储单元可以是连续的也可以是不连续的。此时,数据元素之间并不能反映元素间的逻辑关系,因此在链式存储结构中引进了一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置。

    image-20200804103014534

2.2 算法

2.2.1 算法定义

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。

简单来说,根据一定的条件,对一些数据进行计算,得到需要的结果。

2.2.2 认识算法

在生活中,我们如果遇到某个问题,常常解决方案不是唯一的。

举个简单的例子,比如想从上海去西安,如何去?会有不同的解决方案,我们可以坐飞机,可以坐火车,可以坐汽车,甚至可以步行,不同的解决方案带来的时间成本和金钱成本是不一样的,比如坐飞机用的时间最少,但是费用最高,步行费用最低,但时间最长。

再例如在上海外滩附近买一套汤臣一品,如何付款?也会有不同的解决方案,可以一次性现金付清,也可以通过银行做按揭。这两种解决方案带来的成本也不一样,一次性付清,虽然当时出的钱多,压力大,但是没有利息,按揭虽然当时出的钱少,压力比较小,但是会有利息,而且30年的总利息几乎是贷款额度的一倍,需要多付钱。

在程序中,我们也可以用不同的算法解决相同的问题,而不同的算法的成本也是不相同的。总体上,一个优秀的算法追求以下两个目标:

  • 花最少的时间完成需求。
  • 占用最少的内存空间完成需求。

下面我们用两个小需求体验算法之美。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/** 需求1:计算1到100的和,试用不同的算法解决 */

/**
* 算法1: 执行100次以上,花费时间较多,执行效率略低
*/
public static void algorithm1() {
// 定义sum变量,用于存放和,执行1次
int sum = 0;
// 定义循环常量n,执行1次
int n = 100;
// 循环,执行n+1次,这里执行101次
for (int i = 1; i <= n; i++) {
// 累加i到sum变量中,执行n次
sum += i;
}
// 输出sum,执行1次,只是为了输出结果,可以忽略不计
System.out.println("sum=" + sum);
}

/**
* 算法2:执行3次,花费时间少,执行效率略高
*/
public static void algorithm2() {
// 定义sum变量,用于存放和,执行1次
int sum = 0;
// 定义循环常量n,执行1次
int n = 100;
// 另一种求和方式,转化多个101的相加的问题,1+100,,2+99,3+98,...50+51,执行1次
sum = (n+1) * n/2;
// 输出sum,执行1次,只是为了输出结果,可以忽略不计
System.out.println("sum="+sum);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/** 需求2:计算1到10的阶乘,试用不同的算法解决 */

/**
* 算法1: 递归计算n的阶乘,核心代码只执行10次
*/
public static long fun1(long n){
if (n == 1){
return 1;
}
return n * fun1(n-1);
}

/**
* 算法2: 计算n的阶乘,核心代码只执行1次,占用空间小
*/
public static long fun2(long n){
int result = 1;
for (long i = 1; i <= n; i++) {
result *= i;
}
return result;
}

2.3 两者之间的关系

数据结构指的是“一组数据的存储结构”。

算法指的是“操作数据的一组方法”。

数据结构是为算法服务的,算法是要作用再特定的数据结构上的。

因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。

3. 算法分析

研究算法的最终目的就是如何花更少的时间,如何占用更少的内存去完成相同的需求。

通过上述两个小需求演示了不同算法之间时间耗费和空间耗费上的差异,但我们并不能将时间占用和空间占用量化,因此,接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。

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

3.1 时间复杂度

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

3.1.1 事后分析估算法

在计算机程序编写前,依据统计方法对算法进行估算,经过总结,我们发现一个高级语言编写的程序在计算机上运行所消耗的时间取决于下列因素:

  • 算法采用的策略和方案。
  • 编译产生的代码质量。
  • 问题的输入规模,所谓的问题输入规模就是输入量的多少。
  • 机器执行指令的速度。

由此可见,抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定,那么该算法的执行时间就只和问题的输入规模有关系了。

我么再次以1-100的的求和案例为例,进行分析:

算法1:如果输入量为n为1,则需要计算1次;如果输入量n为1亿,则需要计算1亿次。

算法2:如果输入量为n为1,则需要计算1次;如果输入量n为1亿,则需要计算1次;

因此,当输入规模为n时,第一种算法执行了1+1+(n+1)+n=2n+3次;第二种算法执行了1+1+1=3次。

如果我们把第一种算法的循环体看做是一个整体,忽略结束条件的判断,那么其实这两个算法运行时间的差距就是n和1的差距。

为什么循环判断在算法1里执行了n+1次,看起来是个不小的数量,但是却可以忽略呢?我们来看下一段代码:

1
2
3
4
5
6
7
8
9
10
11
/** 需求3:计算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; // 执行n^2次
}
}
System.out.println("sum="+sum);
}

上面这个例子中,如果我们要精确的研究循环的条件执行了多少次,是一件很麻烦的事情,并且,由于真正计算和的代码是内循环的循环体,所以,在研究算法的效率时,我们只考虑核心代码的执行次数,这样可以简化分析。

我们研究算法复杂度,侧重的是当输入规模不断增大时,算法的增长量的一个抽象(规律),而不是精确地定位需要执行多少次,因为如果是这样的话,我们又得考虑回编译期优化等问题,容易主次跌倒。
我们不关心编写程序所用的语言是什么,也不关心这些程序将跑在什么样的计算机上,我们只关心它所实现的算法。这样,不计那些循环索引的递增和循环终止的条件、变量声明、打印结果等操作,最终在分析程序的运行时间时,最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间,最重要的就是把核心操作的次数和输入规模关联起来。

image-20200804142345950

3.1.2 事前分析估算法

2.1.2.1 函数渐近增长

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

数学概念似乎有点艰涩难懂,那我们以普通人的角度来理解函数渐近增长。

  • 测试1

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

    1. 算法A1要做2n+3次操作,可以这么理解:先执行n次循环,执行完毕后,再有一个n次循环,最后有3次运算。
    2. 算法A2要做2n次操作。
    3. 算法B1要做3n+1次操作,可以这个理解:先执行n次循环,执行完毕后,再执行一个n次循环,执行完毕后 ,再执行一个n次循环,最后再执行1次运算。
    4. 算法B2要做3n次操作。

    那么,上述算法,哪一个更快一些呢?

    image-20200804143644791

    image-20200804143955005

    通过数据表格,比较算法A1和算法B1:

    1. 当输入规模n=1时,A1需要执行5次,B1需要执行4次,所以A1的效率比B1的效率低;
    2. 当输入规模n=2时,A1需要执行7次,B1需要执行7次,所以A1的效率和B1的效率一样;
    3. 当输入规模n>2时,A1需要的执行次数一直比B1需要执行的次数少,所以A1的效率比B1的效率高;

    所以我们可以得出结论:当输入规模n>2时,算法A1的渐近增长小于算法B1的渐近增长。

    通过观察折线图,我们发现,随着输入规模的增大,算法A1和算法A2逐渐重叠到一块,算法B1和算法B2逐渐重叠到一块,所以我们得出结论: 随着输入规模的增大,算法的常数操作可以忽略不计。

  • 测试2

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

    1. 算法C1需要做4n+8次操作。
    2. 算法C2需要做n次操作。
    3. 算法D1需要做2n^2次操作。
    4. 算法D2需要做n^2次操作。

    那么上述算法,哪个更快一些?

    image-20200804144506425

    image-20200804145032783

    通过数据表格,对比算法C1和算法D1:

    1. 当输入规模n<=3时,算法C1执行次数多于算法D1,因此算法C1效率低一些。
    2. 当输入规模n>3时,算法C1执行次数少于算法D1,因此,算法D2效率低一些。

    所以,总体上,算法C1要优于算法D1。

    通过折线图,对比对比算法C1和C2:随着输入规模的增大,算法C1和算法C2几乎重叠 。

    通过折线图,对比算法C系列和算法D系列:随着输入规模的增大,即使去除n^2前面的常数因子,D系列的次数要远远高于C系列。

    因此,可以得出结论:随着输入规模的增大,与最高次项相乘的常数可以忽略。

  • 测试3

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

    1. 算法E1: 2n^2+3n+1。
    2. 算法E2: n^2 。
    3. 算法F1:2n^3+3n+1。
    4. 算法F2: n^3 。

    那么上述算法,哪个更快一些?

    image-20200804154909208

    image-20200804155045897

    通过数据表格,对比算法E1和算法F1:当n=1时,算法E1和算法F1的执行次数一样。当n>1时,算法E1的执行次数远远小于算法F1的执行次数。所以算法E1总体上是由于算法F1的。

    通过折线图我们会看到,算法F系列随着n的增长会变得特块,算法E系列随着n的增长相比较算法F来说,变得比较慢,所以可以得出结论:最高次项的指数大的,随着n的增长,结果也会变得增长特别快。

  • 测试4

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

    1. 算法G:n^3。
    2. 算法H: n^2。
    3. 算法I:n。
    4. 算法J: logn 。
    5. 算法K: 1。

    那么上述算法,哪个效率更高呢?

    image-20200804155406812

image-20200804155526273

通过观察数据表格和折线图,很容易可以得出结论:算法函数中n最高次幂越小,算法效率越高。

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

  • 算法函数中的常数可以忽略。
  • 算法函数中最高次幂的常数因子可以忽略。
  • 算法函数中最高次幂越小,算法效率越高。

2.1.2.2 大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
2
3
4
5
6
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);
}

算法2:

1
2
3
4
5
6
7
8
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);
}

算法3:

1
2
3
4
5
6
7
8
9
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次
}
}
}

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

算法一:3次

算法二:n+3次

算法三:n^2+2次

如果用大O记法表示上述每个算法的时间复杂度,应该如何表示呢?基于我们对函数渐近增长的分析,推导大O阶的表示法有以下几个规则可以使用:

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数中,只保留高阶项。
  3. 如果最高阶项存在,且常数因子不为1,则去除与这个项相乘的常数。

所以,上述算法的大O记法分别为:

算法一:O(1)。

算法二:O(n)。

算法三:O(n^2)。

2.1.2.3 常见大O阶

  • 线性阶:一般含有非嵌套循环涉及线性阶,线性阶就是随着输入规模的扩大,对应计算次数呈直线增长 。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /**
    * 它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次
    */
    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);
    }
  • 平方阶: 一般嵌套循环属于这种时间复杂度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**
    * n=100,也就是说,外层循环每执行一次,内层循环就执行100次,那总共程序想要从这两个循环中出来,就需要执行100*100次。
    * 也就是n的平方次,所以这段代码的时间复杂度是O(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);
    }
  • 立方阶:一般三层嵌套循环属于这种时间复杂度 。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /**
    * n=100,也就是说,外层循环每执行一次,中间循环循环就执行100次,中间循环每执行一次,最内层循环需要执行100次,那总共程序想要从这三个循环中出来。
    * 就需要执行100100100次,也就是n的立方,所以这段代码的时间复杂度是O(n^3).
    */
    public static void main(String[] args) {
    int x = 0,n = 100;
    for (int i = 1; i <=n ; i++) {
    for (int j = 1; j <=n ; j++) {
    for (int j = i; j <=n ; j++) {
    x++;
    }
    }
    }
    System.out.println(x);
    }
  • 对数阶: 对数,属于高中数学的内容,我们分析程序以程序为主,数学为辅,所以不用过分担心。

    1
    2
    3
    4
    int i=1,n=100;
    while(i<n){
    i = i*2;
    }

​ 由于每次i*2之后,就距离n更近一步,假设有x个2相乘后大于n,则会退出循环。由于是2^x=n,得到x=log(2)n,所以这个循环的时间复杂度为O(logn);

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

image-20200804163333562

image-20200804163444172

  • 常数阶: 一般不涉及循环操作的都是常数阶,因为它不会随着n的增长而增加操作次数。
1
2
3
4
5
public static void main(String[] args) {
int n=100;
int i=n+2;
System.out.println(i);
}

上述代码,不管输入规模n是多少,都执行2次,根据大O推导法则,常数用1来替换,所以上述代码的时间复杂度为O(1) 。

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

描述 增长的数量级 说明 举例
常数级别 1 普通语句 两数相加
对数级别 logN 二分策略 二分查找
线性级别 N 循环 找出最大元素
线性对数级别 NLogN 分治思想 归并排序
平方级别 N^2 双层循环 检查所有元素对
立方级别 N^3 三层循环 检查所有三元组
指数级别 2^N 穷举查找 检查所有子集

他们的复杂程度从低到高依次为: O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)

根据前面的折线图分析,我们会发现,从平方阶开始,随着输入规模的增大,时间成本会急剧增大,所以,我们的算法,尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度,而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的,那我们可以分为这种算法是不可取的,需要优化。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 案例1:
* 在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) {
System.out.println(i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 案例2:
* 在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);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 案例3:
* 在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)
*/
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);
}
}

2.1.2.5 最坏情况

从心理学角度讲,每个人对发生的事情都会有一个预期,比如看到半杯水,有人会说:哇哦,还有半杯水哦!但也有人会说:天哪,只有半杯水了。一般人处于一种对未来失败的担忧,而在预期的时候趋向做最坏的打算,这样即使最糟糕的结果出现,当事人也有了心理准备,比较容易接受结果。假如最糟糕的结果并没有出现,当事人会很快乐。

算法分析也是类似,假如有一个需求:有一个存储了n个随机数字的数组,请从中查找出指定的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 需求:有一个存储了n个随机数字的数组,请从中查找出指定的数字。
* 最好情况:查找的第一个数字就是期望的数字,那么算法的时间复杂度为O(1)。
* 最坏情况:查找的最后一个数字,才是期望的数字,那么算法的时间复杂度为O(n)。
* 平均情况:任何数字查找的平均成本是O(n/2)。
*/
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;
}

由此可见,最坏情况是一种保证,在应用中,这是一种最基本的保障,即使在最坏情况下,也能够正常提供服务,所以,除非特别指定,我们提到的运行时间都指的是最坏情况下的运行时间。

3.2 空间复杂度

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

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

    | 数据类型 | 占用内存字节数 |
    | ——– | ————– |
    | byte | 1 |
    | short | 2 |
    | int | 4 |
    | long | 8 |
    | float | 4 |
    | double | 8 |
    | boolean | 1 |
    | char | 2 |

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

    image-20200804165752597

  2. 计算机访问内存的方式都是一次一个字节。例如: Date date = new Date(),则date这个变量需要占用8个字节来表示 。

  3. 创建一个对象,比如new Date(),除了Date对象内部存储的数据(例如年月日等信息)占用的内存,该对象本身也有内存开销,每个对象的自身开销是16个字节,用来保存对象的头信息。

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

    image-20200804165719086

  5. Java中数组被被限定为对象,他们一般都会因为记录长度而需要额外的内存,一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销,4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

了解了java的内存最基本的机制,就能够有效帮助我们估计大量程序的内存使用情况。

算法的空间复杂度计算公式记作:S(n)=O(f(n)),其中n为输入规模,f(n)为语句关于n所占存储空间的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/** 需求:对指定的数组元素进行反转,并返回反转的内容,要求使用不用的空间复杂度。*/

/**
* 算法1:不管传入的数组大小为多少,始终额外申请4+4=8个字节。空间复杂度为O(1)。
*/
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;
}

/**
* 算法2:4+4n+24=4n+28。空间复杂度为O(n)。
*/
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;
}

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

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

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

支付宝打赏 微信打赏

请作者喝杯咖啡吧