【数算-1】复杂度、对数器、二分法、排序算法

川长思鸟来 2022-10-08 05:52 106阅读 0赞

# 1. 复杂度 #

复杂度我们一般考虑的是最坏情况

我们对常数时间操作以及非常数时间操作的基本数量就是“Big O” **时间复杂度**。

**常数时间操作**：例如数组寻址 >>带符号右移，>>> 不带符号右移。

**非常数时间操作**：

还有一点：

异或操作是无进位相加

**额外空间复杂度**：与空间无关，是自己在操作的时候额外开辟的内存。

**常数项**：一些细枝末节的问题，随机大样本可以去测试出来，直接跑！！！

最优解是 **时间复杂度**、**额外空间复杂度**、**常数项**的总和评价，其中，时间复杂度是核心，也是最重要的！！！

# 2. 对数器 #

对数器就是对我们的方法进行测试的工具。

# 3. 二分法 #

**要求：**  
１、数据量大，且有序  
２、注意边界条件

## 找指定的数字： ##

public static void main(String[] args) {
        
            int[] b = {
        1, 8, 9, 3, 1, 8, 9, 3, 9, 6, 6};
            int[] c = {
        1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 19, 22, 46};
    
            System.out.println(findOddNum(c, 7));
        }
    
        public static int findOddNum(int[] arr, int value) {
        
            // 验证数据是否可靠
            if (arr == null || arr.length == 0) {
        
                return -1;
            }
    
            int L = 0;
            int R = arr.length - 1;
            int mid = 0;
            int index = -1;
    
            while (L <= R) {
        
                mid = L + ((R - L) >> 1);
                if (arr[mid] <= value) {
        
                    index = mid;
                    L = mid + 1;
                } else {
        
                    R = mid - 1;
                }
            }
            return index;
        }

// 二分查找的递归实现（https://time.geekbang.org/column/article/42520）
    public int bsearch(int[] a, int n, int val) {
        
      return bsearchInternally(a, 0, n - 1, val);
    }
    
    private int bsearchInternally(int[] a, int low, int high, int value) {
        
      if (low > high) return -1;
    
      int mid =  low + ((high - low) >> 1);
      if (a[mid] == value) {
        
        return mid;
      } else if (a[mid] < value) {
        
        return bsearchInternally(a, mid+1, high, value);
      } else {
        
        return bsearchInternally(a, low, mid-1, value);
      }
    }

## 二分法找最小值： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70]

二分中出现重复数字的情况：

public int bsearch(int[] a, int n, int value) {
        
      int low = 0;
      int high = n - 1;
      while (low <= high) {
        
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
        
          high = mid - 1;
        } else if (a[mid] < value) {
        
          low = mid + 1;
        } else {
        
          if ((mid == 0) || (a[mid - 1] != value)) return mid;
          else high = mid - 1;
        }
      }
      return -1;
    }

# 4. 几种简单的排序算法 #

> 选择冒泡插入，插入最优  
> 快排归并，快排分区分治很优秀  
> 桶计数，划分区域在范围内排序，计数省去排序

## 选择排序法 ##

选择排序就是遍历所有元素，选出最小的一个来排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 2]

## 冒泡排序 ##

冒泡排序就是涉及到一个互换的操作，一直和身边的人比，把最大的排在最后的做法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 4]

## 插入排序 ##

从小范围的有序到大范围的有序。最后再到整体的有序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 7]

**思路：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 8]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70]: /images/20221005/d71b5d66e678413ea0975aecbbd23c43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 1]: /images/20221005/5a3f2ee1292841b48d1e3a06758a481c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 2]: /images/20221005/870efe514c1e408882027c7e79b142e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 3]: /images/20221005/b5f1af399f78428995d77d0f47cea7bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 4]: /images/20221005/394910b8684c43449e2ee35e24c27cfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 5]: /images/20221005/0d9eaccf298e442ba55534a3d09ba61d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 6]: /images/20221005/e08d2fb176ba487a884006d8f575b8e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 7]: /images/20221005/50391a5171234dcfa7fca5974addc78b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 8]: /images/20221005/3e3d1d5b22ae42a18875e2dc5dcb89c8.png