认识复杂度、对数器、二分法

约定不等于承诺〃 2023-10-08 20:45 44阅读 0赞

## 认识复杂度、对数器、二分法 ##

--------------------

#### 文章目录 ####

*  认识复杂度、对数器、二分法
 *  常数操作
 *   *  常见的常数实现操作：
 *  时间复杂度
 *  选择排序
 *   *  选择算法思路
     *  选择排序的代码实现
 *  冒泡排序
 *   *  冒泡算法思路
     *  代码实现
 *  插入排序
 *   *  插入算法思路
     *  代码实现
 *  额外的空间复杂度
 *  算法流程的常数项
 *  算法的最优解
 *   *  时间复杂度从好到差的排名
 *  对数器的认识
 *  认识二分法
 *   *  二分法的代码实现

--------------------

## 常数操作 ##

**评估算法的优劣指标**

> 1.时间复杂度（流程决定）  
> 2.额外空间复杂度（流程决定）  
> 3.常数项时间（实现细节决定）

--------------------

常数时间的操作指的是固定时间的操作

> 例如：  
> 有两个int型整数的a,b相加  
> 在Java中由于int型都占32位，所以a+b 位数一样 因此是固定时间  
> 在数组中的寻址，在内存中是连续区间，直接根据偏移量去寻找，直接去找200万位置的数组也是常数时间

### 常见的常数实现操作： ###

> •常见的算术运算 （+、-、\*、/、%）  
> •常见的位运算（>>、>>>、<<、|、&、^等）  
> •赋值、比较、自增、自减操作等  
> •数组寻址操作

## 时间复杂度 ##

> 在一个要计算的流程操作中，常数量位为N的话，执行完整个流程操作，用来描述我的常数量操作是个什么样的关系。

## 选择排序 ##

### 选择算法思路 ###

> 在一个整数数组中，长度为N，实现从小到大的排序操作。描述整个算法流程  
> arr\[0~N-1\]范围上，找到最小值，把最大值交换到0位置处。（1次交换）  
> arr\[1~N-1\]范围上，找到最小值，把最大值交换到1位置处。（1次交换）  
> arr\[2~N-1\]范围上，找到最小值，把最大值交换到2位置处。（1次交换）  
> 每一步的操作都是常数级别，交换N次，通过看加比较的方式得出时间复杂度便是一个等差数列：a*N^2+ b*N^2+c  
> 便得到选择排序的时间复杂度就是O(N^2)

### 选择排序的代码实现 ###

public static void selectSort(int[] arr){
        
    	if(arr == null || arr.length < 2){
        
    		return;
    	}
    	for(int i = 0;i < arr.length -1 ;i++){
        
    		int minIndex = i;
    		for(int j = i + 1;j < arr.length;j++){
        
    			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    		}
    		swap(arr,i,minIndex);
    	}
    }
    public static void swap(int[] arr,int i,int j){
        
    	int tmp = arr[i];
    	arr[i] = arr[j];
    	arr[j] = tmp;
    }

## 冒泡排序 ##

### 冒泡算法思路 ###

> 在arr\[0～N-1\]范围上：  
> arr\[0\]和arr\[1\]，谁大谁来到1位置；arr\[1\]和arr\[2\]，谁大谁来到2位置…arr\[N-2\]和arr\[N-1\]，谁大谁来到N-1位置
> 
> 在arr\[0～N-2\]范围上，重复上面的过程，但最后一步是arr\[N-3\]和arr\[N-2\]，谁大谁来到N-2位置  
> 在arr\[0～N-3\]范围上，重复上面的过程，但最后一步是arr\[N-4\]和arr\[N-3\]，谁大谁来到N-3位置 …  
> 最后在arr\[0～1\]范围上，重复上面的过程，但最后一步是arr\[0\]和arr\[1\]，谁大谁来到1位置

很明显，如果arr长度为N，每一步常数操作的数量，依然如等差数列一般。所以，总的常数操作数量 =a\*(N^2)+ b\*N + c (a、b、c都是常数)  
所以冒泡排序的时间复杂度为O(N^2)。

### 代码实现 ###

public static void bobbleSort(int[] arr){
        
    	if(arr == null || arr.length < 2){
        
    		return;
    	}
    	for(int e = arr.length -1 ;e > 0;e--){
        
    		for(int i = 0;i < e; i ++){
        
    			if(arr[i] > arr[i+1]){
        
    				swap(arr,i,i+1)
    			}
    		}
    	}
    }
    public static void swap(int[] arr,int i,int j){
        
    	arr[i] = arr[i] ^ arr[j];
    	arr[j] = arr[i] ^ arr[j];
    	arr[i] = arr[i] ^ arr[j];

## 插入排序 ##

### 插入算法思路 ###

> 想让arr\[0~0\]上有序，这个范围只有一个数，当然是有序的。  
> 想让arr\[0~1\]上有序，所以从arr\[1\]开始往前看，如果arr\[1\]<arr\[0\]，就交换。否则什么也不做。 …  
> 想让arr\[0~i\]上有序，所以从arr\[i\]开始往前看，arr\[i\]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。  
> 最后一步，想让arr\[0~N-1\]上有序，arr\[N-1\]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。  
> 估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。  
> 最差情况估计  
> 最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般；所以，总的常数操作数量 =a\*(N^2)+ b\*N + c (a、b、c都是常数)

### 代码实现 ###

public static void insertionSort(int[] arr){
        
    	if(arr == null || arr.length < 2){
        
    		return;
    	}
    	for(int i = 1;i<arr.length;i++){
        
    		for(int j = i - 1;j >= 0 && a[j] > arr[j+1] ;j--){
        
    			swap(arr,j,j+1);
    		}
    	}	
    }
    
    public static void swap(int[] arr,int i,int j){
        
    	arr[i] = arr[i] ^ arr[j];
    	arr[j] = arr[i] ^ arr[j];
    	arr[i] = arr[i] ^ arr[j];
    }

## 额外的空间复杂度 ##

> 1.算法的过程，和具体的语言是无关的。  
> 2.想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉  
> 3.一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。  
> 4.如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。就是常数时间,开辟空间来办事 最差情况考虑开辟空间的复杂度 注意有限几个变量这个很关键 用户要求不算  
> 5.作为输入参数的空间，不算额外空间。程序员的自主空间;作为输出结果的空间，也不算额外空间。因为这些都是必要的、和现实目标有关的。所以都不算。  
> 6.除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

## 算法流程的常数项 ##

> 当两个算法的时间复杂度一样的时候 拼常数时间 常数项  
> 冒泡 和 插入 插入就是比冒泡快 冒泡排序就是没有插入的好 尽管时间复杂度相同  
> 如何分析？  
> 放弃理论分析 生成随机数直接测试  
> 例如加操作就是没有异或快 除法操作就是没有加号快  
> 常数操作类型是很多的 那就实际跑来估计

## 算法的最优解 ##

> 时间复杂度尽可能低  
> 空间复杂度小  
> 常数时间操作在这两者之外 就比至高处项系数

### 时间复杂度从好到差的排名 ###

> O(1)  
> O(logN)  
> O(N)  
> O(N\*logN)  
> O(N^2) O(N^3) … O(N^K)  
> O(2^N) O(3^N) … O(K^N)  
> O(N!)

## 对数器的认识 ##

> 认识对数器：  
> 1，你想要测的方法a  
> 2，实现复杂度不好但是容易实现的方法b  
> 3，实现一个随机样本产生器  
> 4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样  
> 5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，断点调试，改对方法a和方法b  
> 6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

计算机0~1进行离散是有穷个的

## 认识二分法 ##

> 只要能正确构建左右两侧的淘汰逻辑，就可以使用二分法  
> 估计时间复杂度最差法来估计 下标换算 数组寻址 常数时间 每次砍掉一半查看  
> 常数时间O(1) O(log2N)时间复杂度 简写为 O(logN)

1.  在一个有序数组中，找>=某个数最左侧的位置  
    思想还是不变 二分可以实现

### 二分法的代码实现 ###

public static boolean exist(int[] sortedArr, int num) {
        
    		if (sortedArr == null || sortedArr.length == 0) {
        
    			return false;
    		}
    		int L = 0;
    		int R = sortedArr.length - 1;
    		int mid = 0;
    		// L..R
    		while (L < R) {
         // L..R 至少两个数的时候
    			mid = L + ((R - L) >> 1);
    			if (sortedArr[mid] == num) {
        
    				return true;
    			} else if (sortedArr[mid] > num) {
        
    				R = mid - 1;
    			} else {
        
    				L = mid + 1;
    			}
    		}
    		return sortedArr[L] == num;
    	}