数据结构和算法概述

数据结构分类

传统上,我们可以把数据结构分为 逻辑结构物理结构两大类

逻辑结构

逻辑结构是从具体问题中抽象出来的模型,是抽象意义上的结构,按照对象中数据元素之间的相互关系分类

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

逻辑结构.png

  • 线性结构:线性结构中的数据元素之间存在一对一的关系线性结构.png
  • 树形结构:树形结构中的元素之间存在一对多的层次关系树形结构.png
  • 图形结构:图形结构的数据元素是多对多关系图形结构.png
物理结构

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

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

顺序存储结构存在一定的弊端,就像生活中排队时会有人插队也可能有特殊情况突然离开,这时候整个结构都处于变化,全部都要向前或者后退

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

算法认识

算法就是根据一定的条件,对一些数据进行计算,从而得到需要的结果,在程序中,我们也可以用不同的算法解决相同的问题,而不同的算法的成本也是不相同的,总体上,一个优秀的算法追求一下两个目标

  1. 花最少的时间完成需求
  2. 占用最少的内存空间完成需求
花少的时间

例:计算 1100的和

解法 1:

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

解法 2:

public static void main(String[] args) {
    int i = 1, sum = 100;
    sum = (i + sum) * sum / 2;
    System.out.println(sum);
  }

解法一需要完成:

  1. 定义两个变量
  2. 执行100次加法运算
  3. 打印结果到控制台

解法二需要完成:

  1. 定义两个变量
  2. 执行1次加法运算,1次乘法运算,1次除法运算,总共3次运算
  3. 打印结果到控制台,使用时间更小
花少的空间

例: 计算 10的阶乘

解法 1:

public static void main(String[] args) {
    long result = function(10);
    System.out.println(result);
  }

  public static long function(long n) {
    if (n == 1) {
      return 1;
    }
    return n * function(n - 1);
  }

解法 2:

public static void main(String[] args) {
    long result = function(10);
    System.out.println(result);
  }

  public static long function(long n) {
    long result = 1;
    for (int i = 1; i <= n; i++) {
      result *= i;
    }
    return result;
  }

解法一:

使用递归完成需求,function方法会执行 10次,并且第一次执行未完毕,调用第二次执行,第二次未执行完毕,调用第三次....,需要在栈内存内同时开辟 10块内存分别执行 10function方法

解法二:

使用 for循环完成需求,function方法只会执行一次,最终,只需要在栈内存内开辟 1块内存空间即可,占用空间更小

算法分析

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

时间复杂度分析

我们要计算算法时间消耗情况,首先我们得度量算法的执行时间,主要有两种方法:事后分析估算方法事前分析估算方法

  • 事后分析估算法

就是我们把算法执行若干次,使用计时函数对运算时间进行计算,这种统计方法主要是通过设计好的测试程序和测试数据,利用计算机计时器对不同的算法编制的程序的运行时间进行比较,从而确定算法效率的高低,但是这种方法也有很大的缺陷:必须依据算法实现编制好的测试程序,通常需要花费较多的时间与精力,测试完了如果发现测试的算法是个非常糟糕的算法,那么之前所做的事情就全部白费了,并且不同的测试环境(硬件环境)的差异导致测试的结果非常大

例:

public static void main(String[] args) {
    long star = System.currentTimeMillis();
    int sum = 0, n = 100;
    for (int i = 1; i <= n; i++) {
      sum += i;
    }
    System.out.println("sum =" + sum);
    long end = System.currentTimeMillis();
    System.out.println(end - star);
  }
  • 事前分析估算法

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

  1. 算法采用的策略和方案
  2. 编译产生的代码质量
  3. 问题的输入规模
  4. 机器执行指令的速度

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

再看看计算 1100的和这个例子

第一种:

public static void main(String[] args) {
    //如果输入为1,执行1次
    //如果输入为n,执行n次

    //执行1次
    int sum = 0, n = 100;
    //执行n+1次
    for (int i = 1; i <= n; i++) {
      //执行了n次
      sum += i;
    }
    System.out.println(sum);
  }

第二种:

public static void main(String[] args) {
    //如果输入为1,执行1次
    //如果输入为n,执行1次

    //执行1次
    int i = 1, sum = 100;
    //执行1次
    sum = (i + sum) * sum / 2;
    System.out.println(sum);
  }

当输入规模为 n时,第一种算法执行了 1+1+(n+1)+n=2n+3次,第二种执行了 1+1+1=3次,但如果我们把第一种算法的循环体看做是一个整体,那么其实这两个算法运行时间的差距就是 n1

为什么在 for循环中的 n+1看起来是不小的数目,但却可以忽略,看一个例子

计算 1001+1002+100个3...100100的结果

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 += j;
      }
    }
    System.out.println("sum =" + sum);
  }

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

我们研究算法的复杂度,侧重的是当输入规模不断增大时,算法的增长量是一个抽象(规律),而不是精确地定位需要执行多少次,因为如果是这样的话,我们又得考虑回编译器优化等问题,容易主次颠倒

我们不关心编写程序所使用的语言,不关心这些程序将运行在什么样的计算机上,我们只关心它所实现的算法,这样,不计那些循环索引的递增和循环终止的条件,变量声明,打印结果,最终在分析程序的运行时间的时候,最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤,我们分析一个算法的运行时间,最重要的就是把 核心操作的次数输入规模关联起来
时间增长度图.png

重点几个结论
  • 随着输入规模的增大,算法的常数操作可以忽略不计

    • 例:$2n+1=2n$,$3n+3=3n+1$
  • 随着输入规模的增大,与最高次项相乘的常数可以忽略

    • 例:$4n+1=n$,$2n^2+1=n^2$
  • 最高次项的指数大的,随着 n的增长,结果也会变得增长特别快

    • 例:$2n^n+3n+1<2n^3+3n+1$,$n^2<n^3$
  • 算法函数中 n最高次幂越小,算法效率越高

    • 例:$1<\log(n)<\ln(n)<n^2 < n^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)$增长最慢的算法为最优算法

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

例:

算法一:$O(2)=O(1)$

public static void main(String[] args) {
    //执行1次
    int sum = 0, n = 100;
    //执行1次
    sum = (n + 1) * n / 2;
    System.out.println(sum);
  }

算法二:$O(n+1)=O(n)$

public static void main(String[] args) {
    //执行1次
    int sum = 0, n = 100;
    for (int i = 1; i <= n; i++) {
      //执行了n次
      sum += i;
    }
    System.out.println(sum);
  }

算法三:$O(n^2+1)=O(n^2)$

public static void main(String[] args) {
    //执行1次
    int sum = 0, n = 100;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        //执行n^2次
        sum += i;
      }
    }
    System.out.println("sum =" + sum);
  }
常见的大O阶

1.线性阶

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

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

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 =" + sum);
  }

3.立方阶

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

int sum = 0, n = 10;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        for (int e = 1; e <= n; e++) {
          sum++;
        }
      }
    }
    System.out.println("sum =" + sum);
  }

4.对数阶

public static void main(String[] args) {
    int i = 1, n = 100;
    while (i < n) {
      i *= 2;
    }
  }

对于对数阶,由于随着输入规模$n$的增大,不管底数为多少,他们的增长趋势都是一样的,所以我们会忽略底数,从而变为$log(n)$

5.常数阶

一般不涉及循环操作的都是常数阶,因为它不会随着$n$的增长而增加操作次数

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

它们的复杂程度从低到高依次为:$O(1)<O(log(n))<O(n)<O(nlog(n))<O(n^2)<O(n^3)$

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

函数调用的时间复杂度

我们在实际开发中不可能只有单个函数,算法代码的时间复杂度,肯定是有函数调用的

例1.

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

  public static void show(int i) {
    System.out.println(i);
  }

main方法中,有一个 for循环,循环体调用了 show方法,由于 show方法内部只执行了一行代码,所有 show方法的时间复杂度为$O(1)$,那 main方法的时间复杂度就是$O(n)$

例2.

public static void main(String[] args) {
    int n = 10;
    for (int i = 0; i < n; i++) {
      show(i);
    }
  }

  public static void show(int i) {
    for (int j = 0; j < i; j++) {
      System.out.println(j);
    }
  }

main方法中,有一个 for循环,循环体调用了 show方法,由于 show方法内部也有一个 for循环,所有 show方法的时间复杂度是$O(n)$,那么 main方法的时间复杂度为$O(n2)$

例3.

public static void main(String[] args) {
    int n = 10;
    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);
      }
    }
  }

  public static void show(int i) {
    for (int j = 0; j < i; j++) {
      System.out.println(j);
    }
  }

show方法中,有一个 for循环,所以 show方法的时间复杂度为$O(n)$,show(n)这行代码的时间复杂度为$O(n)$,第一个 for循环的时间复杂度为$O(n^2),$第二个两层嵌套循环的时间复杂度为$O(n^2)$,所以总得时间复杂度为$O(2n^2+n)$,但根据 大O推导规则,所以最终 main方法的时间复杂度为$O(n^2)$

最坏情况

我们生活中遇到事情一般都会有最坏情况与最好情况,算法分析也是类似的,也有可能出现最坏情况或最好情况

例:有一个存储了$n$个随机数字的数组,请从中查找出指定的数字

public static void main(String[] args) {
    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(\frac{n}{2})$

算法的空间复杂分析

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

JAVA中常见内存占用
数据类型内存占用字节数
byte1
short2
int4
long8
float4
double8
boolean1
char2
  1. 一个引用(机器地址)需要$8$个字节表示:

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

  1. 创建一个对象,比如new Date(),除了Date对象内部存储的数据(例如年月日等信息)占用的内存,该对象本身也有内存开销,每个对象的自身开销是$16$个字节,用来保存对象的头信息
  2. 一般内存的使用,如果不够$8$个字节,都会被自动填充为$8$字节
//对象本身占用16字节
public class A {
  //整型成员变量a占用4个字节
  public int a = 1;
}
//那么创建该对象总共需要20个字节,但由于不是以8为单位,所以会自动填充为24个字节
  1. java中数组被限定为对象,他们一般都会因为记录长度而需要额外的内存,一个原始数据类型的数组一般需要$24$字节的头信息($16$个自己的对象开销,$4$字节用于保存长度以及$4$个填充字节),再加上保存值所需的内存
算法的空间复杂度

了解java的内存最基本的机制,就能够有效帮助我们估计大量程序的内存使用情况,算法的空间复杂度计算公式记作:$S(n)=O(f(n))$,其中$n$为输入规模,$f(n)$为语句关于$n$所占存储空间的函数

例:对指定的数组元素进行反转,并返回反转的内容

解法一:空间复杂度为$O(1)=O(8)$

public static int[] reverse1(int[] arr) {
    //申请4个自己
    int n = arr.length;
    //申请4个字节
    int temp;
    for (int star = 0, end = n - 1; star <= end; star++, end--) {
      temp = arr[star];
      arr[star] = arr[end];
      arr[end] = temp;
    }
    return arr;
  }

解法二:空间复杂度为$O(n)=O(4n+28)$

public static int[] reserve2(int[] arr) {
    //申请4个字节
    int n = arr.length;
    //申请n*4个字节+数组自身24个字节
    int[] temp = new int[n];
    for (int i = n - 1; i >= 0; i--) {
      temp[n - i - 1] = arr[i];
    }
    return temp;
  }

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

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

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

Last modification:March 16th, 2021 at 05:00 pm