线性算法与对数算法,数据结构与算法注释

对数器的使用

对数器是通过用大量测试数据来验证算法是否正确的一种方式。在算法笔试的时候，我们经常只能确定我们写出的算法在逻辑上是大致正确的，但是谁也不能一次性保证绝对的正确。特别是对于一些复杂的题目，例如贪心算法，我们往往无法在有限时间内用数学公式来推导证明我们程序的正确性。而且在线的OJ一般只会给出有数的几个简单的 samples ，可能我们的算法在这些简单的 samples 偶然通过了，但是在一些复杂的 samples 处却出现了问题。这时我们无法使用复杂的 samples 来分析调试我们的代码，人工设计样例来测试代码的效率又太低，而且不能确保考虑各种特殊情况。因此，能随机产生不同情况的数据的对数器就派上了用场。

对数器，简而言之，就是一个绝对正确的方法和能产生大量随机样例的随机器的组合。

比如我们前面实现的排序，我们并不确认我们实现的算法是否正确？此时就可以通过对数器进行解决。代码实现如下：

package com.anzhi;

/**
 * 编写一个对数器，用来验证之前的排序算法的正确性。
 * 对数器，简而言之，就是一个绝对正确的方法和能产生大量随机样例的随机器的组合。
 */
public class LogarithmDemo {
    public static void main(String[] args) {
        int maxLength = 5;
        int maxValue = 1000;
        int loopTimes = 10000;

        for (int i = 0; i < loopTimes; i++) {
            int[] arr = lenRandomAndValueRandom(maxLength, maxValue);
            int[] arr2 = copyArray(arr);
            
            // 备份元素
            int[] arrBack = copyArray(arr);
            int[] arr2Back = copyArray(arr2);
            // 使用排序
            selectSortArr(arr);
            insertionSort2(arr2);
            if (!isSorted(arr)) {
                System.out.println("选择排序错误");
                printArr(arrBack);
                break;
            }
            if (!isSorted(arr2)) {
                System.out.println("插入排序错误");
                printArr(arr2Back);
                break;
            }
        }
    }

    // 编写长度、值都随机的一个数组
    public static int[] lenRandomAndValueRandom(int maxLength, int maxValue) {
        int len = (int) Math.random() * maxLength;
        int[] arr = new int[len];

        for (int i = 0; i < len; i++) {
            arr[i] = (int) Math.random() * maxValue;
        }
        return arr;
    }

    // 拷贝数组
    public static int[] copyArray(int[] arr) {
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

    // 判断数组是否相等
    // 这个方法的前提是 arr1 和 arr2 相等
    public static boolean isSorted(int[] arr) {
        if (arr.length < 2) {
            return true;
        }
        int maxValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (maxValue > arr[i]) {
                return false;
            }
            maxValue = Math.max(maxValue, arr[i]);
        }
        return true;
    }
}

上面的排序算法使用的是前面章节实现的排序算法。此时我们故意改一下排序算法，让其出错：


// 对数组进行排序
private static void selectSortArr(int[] arr) {
  // 考虑边界调节，不用排序直接返回
  if (arr == null || arr.length < 2) {
    return;
  }

  // 按照之前的想法，开始找最小值
  // 0 ～ N-1;
  // 1 ～ N-1;
  // 2 ～ N-1;
  int N = arr.length;
  for (int i = 0; i < N - 1; i++) {
    // 0 ~ N-1
    // 1 ~ N-1
    // i ~ N-1
    // 从下标为 i 的开始循环，因此，最小值的下标是 
    int minNumIndex = i;
    // 遍历开始找最小值, 因为一旦左边确认一个最小值后，就不会再动它，因此
    for (int j = i + 1; j < N; j++) {
      // 遍历所有值，找到最小值
      // minNumIndex = arr[j] < arr[minNumIndex] ? j : minNumIndex;
      minNumIndex = arr[j] < arr[minNumIndex] ? minNumIndex : j;
    }
    // 找到最最小值之后要进行数据交换
    swapData(arr, i, minNumIndex);
  }
}

测试输出结果：

选择排序错误
987 299 113 445 576 635 321 347 861 596 157 831 338 711 534 992 434 546 60 834 231 870 16

可以打印出测试案列。然后针对测试案例我们可以进行 debug 排查问题。如果对于这个测试案例觉得太长，我么可以通过修改 maxLength 来改变测试案例的数组元素。

比如将 maxLength 改为 5，再次测试

选择排序错误
947 376 570 207

数据结构与算法跟谁学 (线性算法与对数算法)

对数器的使用