需要一个不用具体的测试数据和测试环境，就可以粗鲁的估计算法的执行效率的方法。这个方法称为复杂度，记做大写的 O （数据结构与算法的精髓）

时间复杂度

用步数作为时间复杂度的计算，步数：可以理解为数组的每次索引值得读取，就算做一步，也称为 unit_time。

案例 1.数组值获取（O（1））

获取数组中第四个位置的值
复杂度 - 图1

  1. int a[] = {0, 1, 2, 3, 4, 5, 6};
  2. System.out.println(a[3]); // step1

step1，获取下标为3的数组值，把这个时间称为1步。 在计算机底层，计算机可以通过一步跳到任意一个索引位置读取数据，这个时间也叫单位时间unit_time。 问题：为什么计算机可以一步读取数据索引值？

时间复杂度：常数时间 —— O（1）
函数图：（表示程序运行时间f（x）与数组长度（x）关系）
复杂度 - 图2

猜数字游戏（O（logN））

步数：logN
对数时间：O（log（N））
数学公式：
复杂度 - 图3

计算N的阶乘（O（N））

复杂度 - 图4

  1. public int factorial(int n) {
  2.     int result = 1; //step1
  3.     for (int i = 1; i <= n; i++) { //step2
  4.         result *= i;  // step3
  5.     }
  6.     return result;
  7. }

复杂度 - 图5
image.png
复杂度 - 图7

计算数组中所有组合方式（O（N^2））

复杂度 - 图8

  1. public void combine(String args[]) {
  2.     for (int i = 0; i < args.length; i++) { //step1
  3.         for (int j = i + 1; j < args.length; j++) { //step2
  4.             System.out.println(args[i] + args[j]); //step3
  5.         }
  6.     }
  7. }

复杂度 - 图9
image.png

总结

  • 规律：只保留最大趋势公式，指数>线性>对数>常数
  • 计算复杂度的时候只看for循环嵌套情况。
  • 写代码的时候，线性复杂度代替指数复杂度就是大大的性能优化

    空间复杂度

    以一个基础数据类型值作为一个基础单位。
    O（1）
    1. int a = 0;
    2. int j = 0;
    O（N）
    1. int a[] = new int[n]

    优先考虑时间复杂度

    因为计算机内存足够大，（摩尔定律）。

    性能优化案例——二分法查找

    线性查找O(N)

    复杂度 - 图11
    1. public static int find(int[] array, int aim) {
    2.   for (int i = 0; i < array.length; i++) {
    3.       if (aim == array[i]) {
    4.           return i;
    5.       }
    6.   }
    7.   return -1;
    8. }

    二分查找O（log（N））

    复杂度 - 图12
    1. public static int find(int[] array, int aim) {
    2.   // 初始化left = 最左侧, right = 最右侧
    3.   int left = 0;
    4.   int right = array.length - 1;
    5.   // 当left > right则表示遍历完成
    6.   while (left <= right) {
    7.       // 获取中间的值
    8.       int middle = (left + right) / 2;
    9.       int middleValue = array[middle];
    10.       if (middleValue == aim) {
    11.           // 已经找到目标
    12.           return middle;
    13.       } else if (middleValue < aim) {
    14.           // 目标在middle的右侧，重置left
    15.           left = middle + 1;
    16.       } else {
    17.           // 目标在middle的左侧，重置right
    18.           right = middle - 1;
    19.       }
    20.   }
    21.   return -1;
    22. }
    性能对比：
    image.png

    练习匹配字符串

    str1.compareTo(str2)
    返回值为负数表示str1在str2前面，反之在后面。
    1. "Kelly".compareTo("Kevin")  // 结果为-10
    2. "Kevin".compareTo("Kelly")  // 结果为10
    ```java import java.util.ArrayList; import java.util.Comparator;

public class Address {

public static int find(ArrayList array, String aim) { int left =0; int right = array.size() - 1; while(left<right){ int middle = (left + right)/2 ;

  1.   String value =  array.get(middle);
  2.   if(value.compareTo(aim)==0){
  3.     return middle;
  4.   }else if(value.compareTo(aim)<0){
  5.     left = middle + 1;
  7.   }else{
  8.     right = middle - 1 ;
  9.   }
  10. }
  12. return -1;

}

public static void main(String[] args) { ArrayList array = new ArrayList<>(); array.add(“Allen”); array.add(“Emma”); array.add(“James”); array.add(“Jeanne”); array.add(“Kelly”); array.add(“Kevin”); array.add(“Mary”); array.add(“Natasha”); array.add(“Olivia”); array.add(“Rose”);

  1. int result1 = find(array, "Kelly");
  2. if (result1 == -1) {
  3.   System.out.println("Kelly 不存在名单中");
  4. } else {
  5.   System.out.println("Kelly 存在名单中，位置是 " + result1);
  6. }
  8. int result2 = find(array, "Edith");
  9. if (result2 == -1) {
  10.   System.out.println("Edith 不存在名单中");
  11. } else {
  12.   System.out.println("Edith 存在名单中，位置是 " + result2);
  13. }

} }

  1. <a name="14Lk1"></a>
  2. ## 性能优化案例——二次问题

数字数组为：[0, 8, 2, 3, 5, 6, 2, 10, 8] 重复数字为：[8, 2]

  1. <a name="OEW7I"></a>
  2. ### 暴力破解(O（N^2）)
  3. 每次取一个元素，依次判断和之后的元素是否有重复。<br />![](https://cdn.nlark.com/yuque/0/2020/svg/316618/1593053848595-8d5a5edb-be92-4413-8fa4-dd5728caf11d.svg#align=left&display=inline&height=351&margin=%5Bobject%20Object%5D&originHeight=351&originWidth=547&size=0&status=done&style=none&width=547)
  4. ```java
  5. public static ArrayList<Integer> repeat(int[] array) {
  6.     ArrayList<Integer> result = new ArrayList<>();
  7.     for(int i = 0; i < array.length; i++){
  8.         // 以此判断i位置元素和后面j位置元素是否相等
  9.         for(int j = i + 1; j < array.length; j++){
  10.             if(array[i] == array[j]){
  11.                 result.add(array[i]);
  12.             }
  13.         }
  14.     }
  15.     return result;
  16. }

标记法(O(N))

申明一个标记数组用来标记每个数是否重复。
复杂度 - 图14
空表示不存在，1表示存在。
复杂度 - 图15

  1. public static ArrayList<Integer> repeat(int[] array) {
  2.     //保存重复值
  3.     ArrayList<Integer> result = new ArrayList<>();
  4.     int[] exists = new int[11];
  5.     for (int i = 0; i < array.length; i++) {
  6.         int value = array[i];
  7.         // 如果当前位置已经为1，则表示重复
  8.         if (exists[value] == 1) {
  9.             result.add(value);
  10.         } else {
  11.             // 否则将当前位置设置为1
  12.             exists[value] = 1;
  13.         }
  14.     }
  15.     return result;
  16. }

image.png
空间换时间的经典案例

字符串查重

  1. import java.util.ArrayList;
  3. public class Second {
  5.   public static ArrayList<Character> repeat(String str) {
  6.     ArrayList<Character> result = new ArrayList<>();
  7.     int extists []= new int [26];
  8.     for (int i=0;i<str.length() ;i++ ){
  9.       char value = str.charAt(i);
  10.       // 或者if (extists[value-'a']==1){   字母a 的ascll码值为97
  11.       if (extists[value-97]==1){
  12.         result.add(value);
  13.       } else{
  14.          extists[value-97]=1;
  15.       }
  16.     } 
  17.     return result;
  18.   }
  20.   public static void main(String[] args) {
  21.     String str = "abcdkioudofanzdfpqwe";
  22.     System.out.println(repeat(str));
  23.   }
  24. }