数据结构和算法中的基本常识

公众号merlinsea

• 什么是数据结构
  

• 数据结构指的是数据相互之间的一种或者多种特定的关系数据元素集合。通俗一点就是说，计算机对数据进行存储时候并不是杂乱没有顺序的，而是具有一定的规则，一个或者多个的数据元素之间就一定拥有一定的关系，所以说数据结构是计算机的存储和组织数据的方式。

• 什么是算法
  

• 算法是针对底层特点的数据结构设计出来的求解问题的步骤，就对于程序而言，算法就是程序的灵魂，优秀的算法可以在面对大量数据计算时，依旧能够保持高速的计算。但是如果对数据量大的程序，我们就需要对时间和空间有要有效的利用，也就是设计一个高效的算法，在同样的硬件设备的情况下，有时候会把速度提高十倍甚至上百倍。

• 程序 = 数据结构 + 算法
  

• 在计算机里来说，如果把单独的数据结构和算法拿出来讨论其实意义不大，就像鱼离不开水，算法也离不开数据结构。如果数据之间没有任何结构的话，算法也就无法实现了，毫无意义了。当然即使数据之间有关系，但是不基于这些数据针对特定的问题设计出特定的解题步骤（即算法），那么这些数据的组织方式也毫无意义。

• 
  
• 总之：数据结构和算法必须要针对特定的问题场景做特定的设计，没有万能的数据结构，也没有万能的算法。
  

• 算法的时间复杂度
  

• 时间复杂度是用于评价算法执行快慢的一个指标，如果一个算法的时间复杂度越高，那么这个算法执行相同规模问题所花费的时间也越多。
  
• 时间复杂度并不是算法从开始运行到结束运行所花费的时间，而是指这个算法完成这个问题所需要执行的基本操作的总次数。我们会用这个中次数来衡量我们的时间复杂度。

• 判断一个算法的时间复杂度的方式
  

1. 确定问题的规模n，对于任意一个问题都会有一个问题的规模n，比如找扑克牌的问题，我们的输入数据是54张扑克牌，那么问题的规模n=54。
   
2. 确定算法所需要执行的基本操作有哪些？ 比如找扑克牌问题中，基本操作其实就是遍历每一张牌和看牌的操作。
   
3. 确定实际执行基本操作的次数 和 问题规模n 的函数关系   即求出f(n)
   
4. 确定f(n)的函数数量级的上限O(n)，最终O(n)就是算法的时间复杂度。

• 举例子
  

void fun(int n){
  int i,j,x=0;
  for(i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      x++;
    }
  }
}
void fun(int n){
  int i = 0;
  i++;
}

1. 问题的规模是入参n
   
2. 执行的基本操作是x++
   
3. 实际执行次数 f(n)= n-1 + n-2 + n-3 + ...+ 0 = n(n-1)/2 = n*n/2-n/2
   
4. f(n)数量级的上限是O(n^2)
   

• 常见的时间复杂度数量级排序
  

• O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(n^k)<O(2^n)，可以看出随着规模n的不断变大，执行的效率就越低。
  

• 时间复杂度的优化方向
  

• 如果我们计算出来的时间复杂度是O(n^2)，那么我们必须要将时间复杂度优化到O(nlogn)级别。
  

• 算法的空间复杂度
  
• 如果我们有一个数组，如何我们需要对这个数组进行排序我们改如何做呢？
  

• 第一种方法：新开一个空间，每次都将数组排序以后放在新的内存空间中
  

//空间复杂度是O(n)
int[] sortArray(int[] nums) {
    int[] tempNums = new int[nums.length];//零时辅助数组
    for(int i=0;i<nums.length;i++){
      int idx = 0;//新的零时数组中下标的位置
      for(int j=0;j<=nums.length;j++){
        if(nums[j]<=nums[i]){
          idx++;
        }
      }
      // idx 结果表示原数组中有多少个元素比nums[i]更小
      tempNums[idx]=nums[i];
    }
    //倒回去
    for(int i=0;i<nums.length;i++){
      nums[i] = tempNums[i];
    }
    return nums;
}

• 第二种方法：不新开一个空间，在原始数组的空间中完成排序操作

//空间复杂度是O(1)
void sortArray(int[] nums){
    for(int i=0;i<nums.length;i++){
        int k = i;
        for(int j=i;j<nums.length();j++){
            if(nums[j]<nums[k]){
                k = j;
            }
        }
      // 保证下标k的位置是最小的
        swap(nums[i],nums[k]); //交换
    }
}

• 空间复杂度
  

• 空间复杂度是指我们程序在完成指定功能的过程中，需要额外开辟的空间，如果程序中涉及的额外空间与问题规模n无关，那么空间复杂度就是O(1)常数级别，如果设计的空间复杂度与n是相关，比如第一中排序方法，那么就是O(n)。
  
• 在实际的开发过程中，我们很少考虑空间复杂度，因为现代的存储设备已经远远可以满足我们日常开发需要，一般我们都会利用空间来换时间，即宁可花更多的空间也要减少程序的时间开销，动态规划