前言

算法:任何良定义的计算和过程。一般来说,问题陈述说明期望的输入/输出关系,算法则描述一个特定的计算过程来实现该输入/输出关系。

数据结构:一种储存和组织数据的方式,旨在便于访问和修改。

算法基础

循环不变式

  • 证明三条性质来理解算法的正确性。

    • 初始化:循环第一次迭代时,它为真。
    • 保持:如果循环的某次迭代之前为真,那么下次迭代之前它仍为真。
    • 终止:循环中止时,不变式提供一个有用的性质来证明算法是正确的。
  • 插入排序

    • 对少量元素排序,该算法是有效算法。是原址排序。
    • 实现目的:往一个有序数组中插入一个数过后,数组仍然有序。
    • 使用循环不变式验证算法:

      • 循环不变式:A[1...j-1]就是原来在位置1到j-1的元素,且已按序排列,我们把这个性质形式地表现为一个循环不变式。
      • 初始化:在第一次迭代循环之前,循环不变式成立。最开始A[1..j]其实只有元素A[1],实际上就是A[1]原来的元素,而且它是有序的(因为只有它一个嘛lol)。
      • 保持:每次迭代循环时,插入一个数,并将其放到合适的位置,此时子数组A[1..j]由原来在A[1...j]中的元素组成,且已按序排列。那么for循环的下一次迭代增加j将保持循环不变式。
      • 终止:循环终止条件是j>A.length = n。又因为每次循环迭代j增加1,所以必有j = n + 1 。在循环不变式中就变成了A[1...n]由原来在A[1...n]中的元素组成,且已按序排列,故算法正确。
    • 代码实现:

      <details>
      <summary>普通版</summary>

  
          
            public static void insertionSort(int[] nums)
            {
                for(int i = 1; i < nums.length; i++)
                {
                    int key = nums[i];
                    int j = i - 1;
        
                    while(j >= 0 && nums[j] > key)
                        nums[j + 1] = nums[j--];
        
                    nums[j + 1] = key;
                }
            }
          
    </details>

    <details>
      <summary>***递归版***</summary>
      <pre><code>  
    public static void recursiveInsertionSort(int[] nums)
{
    recursiveInsertionSort(nums, nums.length - 1);
}

    private static void recursiveInsertionSort(int[] nums, int x)
    {
        if (x == 0)
            return;

        recursiveInsertionSort(nums, x-1);

        int tmp = nums[x];
        int index = x - 1;

        while(index >= 0 && tmp < nums[index])
            nums[index + 1] = nums[index--];

        nums[index + 1] = tmp;
    }
      </code></pre>
    </details>

分析算法

预测算法所需资源

  • 输入规模:依赖于研究的问题
  • 运行时间:执行的基本操作或者步数。比如遍历一次长度为n的数组,那么这一句的运行时间就为n。

    • 增长量级/增长率:计算效率时,常量因子不如增长率重要,当我们忽略低阶项和最重要的项的常系数时,如果一个算法最坏情况运行的时间为an² + bn + c,那么运行时间为Θ(n²)。

设计算法

  • 增量:插入排序使用了增量方法

    在排序子数组A[1...j - 1]后,将单个元素A[j]插入子数组适当的位置,产生排序好的子数组A[1...j]

  • 分治法:归并排序算法完全遵循分治法。

    许多算法在结构上是递归的,为了解决给定的问题,算法一次或者多次调用自身以解决若干子问题,而它们大多数都遵循了分治法的思想。

    • 分治模式:

      • 分解原问题为若干子问题,这些子问题是原问题的规模较小的实例。
      • 解决这些子问题,递归地求解各子问题。若子问题的规模足够小,则直接求解。
      • 合并 这些子问题的解成原问题的解。
    • 归并排序:

      • 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。(二分法)
      • 解决:使用归并排序递归地排序两个子序列。
      • 合并:合并两个已排序的子序列以产生已排序的答案。
    • 代码实现:

    <details>

      <summary>***点击查看代码***</summary>
  
        public static void mergeSort(int[] nums)
        {
        mergeSort(nums, 0, nums.length -1);
        }

        public static void mergeSort(int[] nums, int left, int right)
        {
            int[] tmp = new int[right - left + 1];
    
            if (left >= right)
                return;
    
            int mid = (left + right) / 2;
    
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
    
            int i = left;
            int j = mid + 1;
            int k = 0;
    
            while (i <= mid && j <= right)
            {
                if (nums[i] < nums[j])
                    tmp[k++] = nums[i++];
                else
                    tmp[k++] = nums[j++];
            }
    
            while(i <= mid)
                tmp[k++] = nums[i++];
    
            while(j <= right)
                tmp[k++] = nums[j++];
    
            for(int l = 0; l < tmp.length; l++)
                nums[l + left] = tmp[l];
        }
          
    </details>
- 扩展

    <details>
      <summary>***分治法版插入排序***</summary>
      <pre><code>  
    public static void mergeInsertionSort(int[] nums, int limit)
{
    mergeInsertionSort(nums, 0, nums.length, limit);
}

    public static void mergeInsertionSort(int[] nums, int left, int right, int limit)
    {
        if(left > right)
            return;

        int mid = (right - left) / 2;

        if (mid < limit)
            return;

                    mergeInsertionSort(nums,left,mid,limit);
        mergeInsertionSort(nums,mid + 1,right,limit);

        for(int i = left + 1; i < right; i++) {
            int key = nums[i];
            int j = i - 1;

            while(j >= 0 && nums[j] > key)
                nums[j + 1] = nums[j--];

            nums[j + 1] = key;
        }
    }
    
      </code></pre>
    </details>
Last modification:July 20th, 2020 at 08:39 am
请随意~