今天看数据结构里面的时间复杂度的时候，有看到 O(logn)。 

对数的定义

如果 



，即a的x次方等于N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作



。其中，a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”。


	
特别地，我们称以10为底的对数叫做常用对数（common logarithm），并记为lg。
	
	

	
称以无理数e（e=2.71828...）为底的对数称为自然对数（natural logarithm），并记为ln。
	
	

	
零没有对数。 [2] 
	
	

	
在实数范围内，负数无对数。 [3]  在虚数范围内，负数是有对数的。
	
 

相关的教学视频：戳这里

对数器在无法进行数据校验的情况下起着极为重要的作用，尤其是数据量大的时候。这里使用简单的冒泡排序进行演示
/**
	冒泡排序
	并使用对数器进行校验
	对数器的概念和使用
	0）有一个你想要测的方法a，
	1）实现一个绝对正确但是复杂度不好的方法b，
	2）实现一个随机样本产生器
	3）实现比对的方法
	4）把方法a和方法b比对很多次来验证方法a是否正确。
	5）如果有一个样本使得比对出错，打印样本分析是哪个方法出错
	6）当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
 */
import java.util.Arrays;
public class C01_BubbleSort {
	public static void bubbleSort(int arr[]){
		if(arr==null || arr.length<2){
			return ;
		}
		
		//冒泡排序，第一个和第二个比较、交换，第二个和第三个比较、交换。。。得到最值在最后一个
		//然后同样的做法得到第二个最值。。。
		//时间复杂度O(N^2)，额外空间复杂度O(1)
		for (int i = arr.length-1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if(arr[j]>arr[j+1]){
					swap(arr, j, j+1);
				}
			}
		}
	}
	///对数器及其他方法//
	//一个一定对的排序方法(比如系统的或者简单的容易实现的)
	public static void systemSort(int arr[]){
		Arrays.sort(arr);
	}
	
	//位运算交换数组的两个数
	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]; 
	}
	//打印数组
	public static void printArr(int[] arr){
		for (int i : arr) {
			System.out.print(i+" ");
		}
		System.out.println();
	}
	//产生测试数据
	public static int[] testData(int len,int val){
		int arr[] = new int[len];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((val+1)*Math.random()-(val+1)*Math.random());
		}
		return arr;
	}
	//判断两个数组是否相等
	public static boolean isEqual(int arr1[] ,int arr2[]){
		if(arr1==null||arr2==null || arr1.length==0||arr2.length==0 || arr1.length!=arr2.length){
			return false;
		}
		for (int i = 0; i < arr2.length; i++) {
			if(arr1[i]!=arr2[i]){
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		int len = 10;//测试数组长度
		int val = 100;//测试数据范围
		int times = 500000;//测试数据量
		boolean isOK = true;
		for (int i = 0; i < times; i++) {
			int arr[] = testData(len, val);
			int arr1[] = Arrays.copyOf(arr, len);
			int arr2[] = Arrays.copyOf(arr, len);
			bubbleSort(arr1);
			systemSort(arr2);
			if( ! isEqual(arr1, arr2)){
				printArr(arr1);
				printArr(arr2);
				isOK = false;
				break;
			}
		}
		System.out.println(isOK);
	}
}

对数器的概念和使用
文章目录
对数器的概念和使用
1、介绍
2、使用方法
2.1 创建一个绝对正确的方法
2.2 生成一个随机数组
2.3 copy数组
2.4 判断两数组是否相同
2.5  大样本测试
3、对插入排序进行测试
3.1插入排序
3.2测试结果

1、介绍

在写出一个算法程序的时候，我们往往无法通过手动输入各种各样的测试数据来验证，在OJ平台上也无法找到对应的题目来进行验证。
在一些样本量很大的情况下，我们往往无法考虑到所有的边界情况。
尤其是一些贪心算法是很难通过数学的方式来进行验证的，这时使用对数器来判断算法程序是否正确

2、使用方法
2.1 创建一个绝对正确的方法
​
public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

2.2 生成一个随机数组

​	maxSize为数组的大小，maxValue为数组的元素的大小的范围

public 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 * Math.random());
		}
		return arr;
	}

2.3 copy数组
​
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;
	}

2.4 判断两数组是否相同
​
	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;
	}

2.5  大样本测试
​
public static void main(String[] args) {
		int testTime = 500000;
		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);
			insertionSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

	}


3、对插入排序进行测试
3.1插入排序
​
public static void insertionSort(int[] arr) {
		if(arr.length < 2 || arr == null) {
			return;
		}
		for(int i = 1; i < arr.length; i++) {
			for(int j = i-1; j>=0 && arr[j+1]<arr[j];j--) {
				swap(arr, j+1, j);
			}
		}
	}

3.2测试结果
​		

正确显示NICE
错误显示fuck

对数器的概念及使用

1.有一个你要测的方法a； 

2.实现一个绝对正确即使复杂度不好的方法b； 

3.实现一个随机样本产生器； 

4.实现比对的方法； 

5.把方法a和方法b比对很多次来验证方法a是否正确 

6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错 

7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确

用冒泡排序作为例子：

package basic_class_01;

import java.util.Arrays;
import java.util.Random;

public class bubbleSortWithComparator {
//    冒泡排序部分
    public static void bubbleSort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        for(int i=arr.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }
    public static void swap(int arr[],int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;

    }
//    产生随机数组
    public static int[] generateRandomArray(int maxSize,int maxValue){
//        产生的数组长度为【0-size】
        int[] arr=new int[(int)((maxSize+1)* Math.random())];
        for(int i=0;i<arr.length;i++){
//            产生的数组中的数的范围是【-value-value】
            arr[i]=(int)((maxValue+1)*Math.random())-(int)(maxValue*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 void comparator(int[] arr){
        Arrays.sort(arr);
    }
//    判断两个数组是否相等
    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;
    }
//    打印
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        text time是判断次数
        int textTime=50000;
        int maxSize=100;
        int maxValue=100;
        boolean succeed=true;
        for(int i=0;i<textTime;i++){
            int[] arr1=generateRandomArray(maxSize,maxValue);
            int[] arr2=copyArray(arr1);
            bubbleSort(arr1);
            comparator(arr2);
            if(!isEqual(arr1,arr2)){
                succeed=false;
                break;
            }
        }
//        如果succeed是true那么就会输出nice
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");

            int[] arr = generateRandomArray(maxSize, maxValue);
            printArray(arr);
            bubbleSort(arr);
            printArray(arr);

    }
}




输出实例：