评估算法优劣的核心指标是什么？

  • 时间复杂度(流程决定)
  • 额外空间复杂度(流程决定)
  • 常数项时间(实现细节决定)

常见的常数时间的操作

  • 常见的算术运算(+、、大、%等) 常见的位运算(>>、>>>、<<、|、&、^等)
  • 赋值、比较、自增、自减操作等
  • 数组寻址操作

总之,执行时间固定的操作都是常数时间的操作。
反之,执行时间不固定的操作,都不是常数时间的操作。

如何确定算法流程的总操作数量与样本数量之间的表达式关系?

  • 1,想象该算法流程所处理的数据状况,要按照最差情况来。
  • 2,把整个流程彻底拆分为一个个基本动作,保证每个动作都是常数时间的操作。
  • 3,如果数据量为N,看看基本动作的数量和N是什么关系。

如何确定算法流程的时间复杂度?

当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉, 高阶项的系数也去掉。
记为:O(忽略掉系数的高阶项)

常见的时间复杂度 排名从好到差:

  • O(1)
  • O(logN)
  • O(N)
  • O(N*logN)
  • O(N2) O(N3) O(NK)
  • O(2N) O(3N) O(KN)
  • O(N!)

Master公式

Master公式可以用于计算递归方法的时间复杂度。
适用范围为子过程规模相等的情况，否则不适用。

主方法的表现形式：
T[n] = a*T[n/b] + f(n)---->>>直接记为T[n] = a*T[n/b] + O(Nd)

  • ①当d < logba时，时间复杂度为O(N^(logba))
  • ②当d == logba时，时间复杂度为O((Nd)*logN)
  • ③当d > logba时，时间复杂度为O(Nd)

认识对数器

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

1.选择排序对数器

public class T1 {

    public static void a_selectionSort(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;
    }

    public static void b_sort(int[] arr) {
        Arrays.sort(arr);
    }

    //生成一个最大容量为maxSize，数组最大值为maxValue的随机数组
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    //复制数组
    public static int[] copyArray(int[] arr) {
        if (arr == null) return null;
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }

        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int testTime = 500; //测试次数
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);//生成随机数组
            int[] arr2 = copyArray(arr1);//复制生成的随机数组
            a_selectionSort(arr1);//需要验证的算法
            b_sort(arr2);//使用暴力算法
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "ice!" : "Fucking fucked!");
        int[] arr = generateRandomArray(maxSize, maxValue);

        printArray(arr);

        a_selectionSort(arr);

        printArray(arr);

    }

}

hhhhh