关于java:听说你要卷算法请你先弄明白什么是数据结构什么是算法什么事复杂度

今日指标：

1：可能说出什么是数据结构，什么是算法

2：能说出大 O 工夫复杂度是怎么得来的

3：可能说出工夫复杂度的几个剖析准则并加以理论利用

4：可能说出常见的几种工夫复杂度 O（1），O（n），O（log n），O（n * log n）

5：能了解空间复杂度的剖析形式

1、概念

尽管概念很空洞，然而概念还是须要介绍的：

1. 数据结构是指一组数据的存储构造
2. 算法就是操作数据的办法

这只是形象的定义，咱们来举一个例子，你有一批货物须要运走，你是找小轿车来运还是找卡车来运？这就是数据结构的领域，选取什么样的构造来存储；至于你货物装车的时候是把货物堆放在一起还是分凋谢这就是算法放到领域了，如何搁置货物更有效率更节俭空间。

数据结构和算法看起来是两个货色，然而咱们为什么要放在一起来说呢？那是因为数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上，因而，咱们无奈孤立数据结构来讲算法，也无奈孤立算法来讲数据结构。

想要学习数据结构与算法，首先要把握一个数据结构与算法中最重要的概念：复杂度剖析

2、复杂度剖析

数据结构和算法解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省存储空间。因而执行效率是一个十分重要的考量指标，那如何来掂量代码的执行效率，就是咱们所说的：工夫，空间复杂度剖析。

为什么要进行复杂度剖析？

1：和性能测试相比，复杂度剖析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2：把握复杂度剖析，将能编写出性能更优的代码，有利于升高零碎开发和保护老本。

2.1、大 O 复杂度表示法

算法的执行效率，粗略地讲，就是算法代码执行的工夫，那如何在不间接运行代码的前提下粗略的计算执行工夫呢？

在 IDEA 中创立一个一般的 java 我的项目：algo-pro

在我的项目中创立一个类：com.itheima.complexity.ComplexityAnalysis

（1）先来看一段简短的代码，求：1，2，3，4……n 累加和

/**
  * 求 1~n 的累加和
  * @param n
  * @return
  */
public int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {sum = sum + i;}
    return sum;
}

假如每行代码执行工夫都一样为：timer，那此代码的执行工夫为多少呢：(3n+3)timer，由此能够看进去，所有代码的执行工夫 T(n)与代码的执行次数成正比。

（2）依照该思路咱们接着看上面一段代码

public int sum2(int n) {
    int sum = 0; 
    for (int i=1; i <= n; ++i) {for (int j=1; j <= n; ++j) {sum = sum +  i * j;}
    }
    return sum;
}

同理，此代码的执行工夫为：(3 n^2 + 3n + 3) * timer

因而有一个重要论断：代码的执行工夫 T(n)与总的执行次数成正相干，咱们能够把这个法则总结成一个公式。

T(n) = O(f(n))

解释一下：T(n)示意代码的执行工夫， n 示意数据规模的大小 ，f(n) 示意了代码执行的总次数，它是一个公式因而用 f(n)示意，O 示意了代码执行工夫与 f(n)成正比

因而第一个例子中的 T(n)=O(3n+3)，第二个例子中的 T(n)=O(3 n^2 + 3n + 3)，这就是 大 O 工夫复杂度表示法

大 O 工夫复杂度 实际上并不具体示意代码真正的执行工夫，而是 示意代码执行工夫随数据规模增长的变化趋势 ，所以，也叫作渐进工夫复杂度， 简称工夫复杂度。

当 n 很大时，公式中的低阶，常量，系数三局部并不左右其增长趋势，因而能够疏忽，咱们只须要记录一个最大的量级就能够了，因而如果用大 O 示意刚刚的工夫复杂度能够记录为：T(n)=O(n),T(n)=O(n^2)

2.2、复杂度分析方法

通用的复杂度剖析法令如下：

（1）最大循环准则

大 O 复杂度表示法只代表一种变化趋势，公式中的低阶，常量，系数三局部并不左右其增长趋势，因而能够疏忽，咱们只须要记录一个最大的量级就能够了。因而 剖析一个算法或者一个代码的工夫复杂度时，只需关注循环执行次数最多的那一段代码即可。

（2）加法准则

请剖析一下如下代码的工夫复杂度：

public int sum3(int n) {
    int sum_1 = 0;
    int p = 1;
    for (; p <= 100; ++p) {sum_1 = sum_1 + p;}

    int sum_2 = 0;
    int q = 1;
    for (; q < n; ++q) {sum_2 = sum_2 + q;}
    // O(n)
    int sum_3 = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; ++i) {
        j = 1;
        for (; j <= n; ++j) {sum_3 = sum_3 +  i * j;}
    }
    // O(n^2)
    return sum_1 + sum_2 + sum_3;
}

其中两段最大量级的复杂度别离为 O(n)和 O(n^2)，其后果本应该是：T(n)=O(n)+O(n ^2)，咱们取其中最大的量级，因而整段代码的复杂度为：O(n ^2)，其实也能够基于第一个最大循环准则得出复杂度为 O(n ^2)

也就是说：总的工夫复杂度就等于量级最大的那段代码的工夫复杂度

另外再看一段代码：

public int sum4(int[] nArr, int[] mArr){
    int sum = 0;
    for(int i : nArr) {sum += i;}
    // O(M)
    for(int i : mArr) {sum += i;}
    //O(N)
    return sum;
}

在这个例子中，尽管没有明确阐明数据规模 n，但其实函数参数中两个数组的长度就是咱们所了解的数据规模，而且这个中央呈现了两个数据规模，咱们别离叫做 m，n

依据咱们的剖析准则，这段代码的工夫复杂度为 O(m+n)，它其实也是线性复杂度 O(n) 的一种。

（3）乘法准则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，举个例子

public int sum5(int n) {
    int ret = 0;
    int i = 1;
    for (; i < n; ++i) {ret = ret + func(i);
    }
    // O（n）return ret;
}
public int func(int n) {
    int sum = 0;
    int i = 1;
    for (; i < n; ++i) {sum = sum + i;}
    return sum; //O(N)
}

独自看是:O(n), 因为 func(i)是 O(n)因而整体是:O(n) O(n) = O(n n) = O(n ^2)

因而能够看出：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

2.3、常见的复杂度

尽管代码写法千差万别，然而咱们平时所见的复杂度量级并不多，列举如下：

对于表格中所列举的一些复杂度从上到下当 n 越大时算法执行工夫会急剧减少，工夫会有限增长，常见复杂度的增长曲线如下图

所以咱们个别要关注后面的几种。且在理论工程利用中防止编写出复杂度超高的代码。

（1）O(1)

O(1)并不是指代码只有一行，它是一种常量级复杂度的示意办法，比如说有一段代码如下：

public void test01(int n){
    int i=0;
    int j = 1;
    return i+j;
}

代码只有三行，它的复杂度也是 O(1)，而不是 O(3)

再看如下代码：

public void test02(int n){
    int i=0;
    int sum=0;
    for(;i<100;i++){sum = sum+i;}
    System.out.println(sum);
}

整个代码中因为循环次数是固定的就是 100 次，这样的代码复杂度咱们认为也是 O(1),

因而总结下来就是：只有代码的执行工夫不随着 n 的增大而增大，这样的代码复杂度都是 O(1)，或者说：只有在算法中不存在递归语句，随 n 变动的循环语句等，即便有千万行代码，复杂度也是 O(1)

（2）O(n)

这种复杂度量级随处可见，比方咱们剖析如下代码：

public void test03(int n){
    int i=0;
    int sum=0;
    for(;i<n;i++){sum = sum+i;}
    System.out.println(sum);
}

另外对于 O(n^2)这种复杂度咱们也就很好了解了

（3）O(log n)

对数复杂度十分的常见，但绝对比拟难以剖析，代码如下：

public void test04(int n){
    int i=1;
    while(i<=n){i = i * 2;}
}

复杂度剖析就是要弄清楚代码的执行次数和数据规模 n 之间的关系

依据教训：第四行代码：i = i*2 循环次数最多，因而咱们要剖析出第四行代码执行了多少次咱们就得出了此代码的工夫复杂度

那第四行代码执行了多少次呢？代码执行第一次 i =2，执行第二次 i =4，执行第三次 i =8………，i 的取值其实是一个等比数列的模式，如图

由图中剖析可知，代码的工夫复杂度示意为

那如果将代码进行批改为如下：

public void test04(int n){
    int i=1;
    while(i<=n){i = i * 3;}
}

（4）O(n * log n)

剖析完 O(log n)，那 O(n * log n)就很容易了解了，比方下列代码：

public void test05(int n){
    int i=0;
    for(;i<=n;i++){test04(n);
    }
}
public void test04(int n){
    int i=1;
    while(i<=n){i = i * 2;}
}

这是一种十分常见的算法工夫复杂度，咱们后续要学习的归并排序，疾速排序的工夫复杂度都是 O(nlogn)

2.4、最好 / 最坏 / 均匀复杂度

（1）最好 / 最坏复杂度

有一个需要：在数组 array 中查找变量 x 的地位，实现如下：

// 其中 n 示意数组 array 的长度
public int getX(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {if (array[i] == x) {pos = i;}
  }
  return pos;
}

通过之前学习的复杂度剖析形式，咱们能够剖析进去这段代码的复杂度为 O(n)，然而这段代码实现的并不是特地好，咱们稍作优化，因为在数组中查找某一元素并不需要把整个数组都遍历一遍，因为可能在遍历的途中就曾经找到了，找到了就间接返回，提前结束循环，优化后的后果如下：

// 其中 n 示意数组 array 的长度
public int getX(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(n)吗？

要查找的变量 x 在可能在数组中的任意地位，如果数组中的第一个元素就是咱们要找的变量 x，那就不须要持续变量余下的 n - 1 个元素了，那复杂度为 O(1), 如果数组中不存在变量 x 那须要残缺的遍历一遍数组，那复杂度就是 O(n)。所以：在不同的状况下，同一段代码的复杂度并不一样

因而咱们须要引入三个概念：最好状况复杂度，最坏状况复杂度，和均匀状况复杂度

最好状况复杂度：在最现实的状况下代码的工夫复杂度

最坏状况复杂度：在最蹩脚的状况下代码的工夫复杂度

（2）均匀状况复杂度

咱们晓得最好或者最坏状况复杂度别离对应了两种极其的状况，产生的概率并不大，为了更好的示意均匀状况下的复杂度，咱们引入均匀状况复杂度。

那刚刚的代码如何剖析评估状况复杂度呢？

// 其中 n 示意数组 array 的长度
public int getX(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;
}

查找变量 x 在数组中的地位有 n + 1 中状况，在数组中 0~n- 1 的地位上以及不在数组中，咱们把每一种状况下代码须要遍历的次数加起来，而后除以 n + 1 就失去了代码须要遍历执行的平均值。如图：

咱们晓得，在大 O 复杂度标记法中，能够省略系数，低阶，常量，因而把该后果简化之后失去的复杂度依然为 O(n)

此时，论断尽管正确，然而计算过程略微有点儿问题，问题出在哪里？就是咱们刚刚讲到的这 n + 1 种状况呈现的概率并不是一样的，

通过之前的解说咱们晓得查找变量 x 在数组中的地位要么在数组中，要么不在数组中，意味着在数组中 0~n- 1 地位上呈现的概率为 1 /2，不再数组中呈现的概率为 1 /2,

此外在数组中 0~n- 1 地位上每一种状况下的概率为 1 /n，因而依据概率法令，要查找的数据呈现在 0 ~ n- 1 中任意地位的概率为 1 /2n

所以后面的论断推导过程中咱们须要将概率思考进去，那计算均匀工夫复杂度的计算过程就变成了这样：

这个值在概率论中叫 加权平均值，也叫做期望值，所以均匀工夫复杂度也叫冀望工夫复杂度，同样的情理如果用大 O 表示法来示意，加权工夫复杂度依然为：O(n)

实际上：大多数状况下，咱们不须要去辨别最好 / 最坏 / 均匀 工夫复杂度，只有在同一段代码块在不同状况下的复杂度有量级的差距时才须要用这三种复杂度来加以辨别

2.5、空间复杂度

工夫复杂度示意了算法的执行工夫与数据规模之间的增长关系 ，类比一下， 空间复杂度全称是渐进空间复杂度，示意算法占用的额定存储空间与数据规模之间的增长关系

用一段小的代码来阐明一下：

public void test(int n){
    int i=0;
    int sum=0;
    for(;i<n;i++){sum = sum+i;}
    System.out.println(sum);
}

代码执行并不需要占用额定的存储空间，只须要常量级的内存空间大小，因而空间复杂度是 O(1)

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {a[i] = i * i;
  }
  for (i = n-1; i >= 0; --i) {System.out.println(a[i]);
  }
}

代码第二行，申请一个空间存储变量 i，然而是常量阶的，跟数据规模 n 没有关系，第三行申请了一个大小为 n 的 int 数组，此外前面的代码简直没有占用更多的空间，因而整段代码的空间复杂度就是 O(n)

咱们 常见的空间复杂度就是 O(1),O(n),O(n ^2)，其余像对数阶的复杂度简直用不到，因而空间复杂度比工夫复杂度剖析要简略的多。因而把握这些足够。

本文由传智教育博学谷 – 狂野架构师教研团队公布，转载请注明出处！

如果本文对您有帮忙，欢送关注和点赞；如果您有任何倡议也可留言评论或私信，您的反对是我保持创作的能源