Function of logarithm

Logarithm is a way to verify whether the algorithm is correct by using a large number of test data. In the written test of the algorithm, we often can only be sure that the algorithm we write is logically roughly correct, but no one can guarantee the absolute correctness at one time. Especially for some complex problems, such as greedy algorithm, we often can't deduce and prove the correctness of our program with mathematical formula in limited time. Moreover, online OJ generally only gives a few simple samples. Our algorithm may pass by chance in these simple samples, but there are problems in some complex samples. At this time, we can't use complex samples to analyze and debug our code. The efficiency of manually designing samples to test the code is too low, and we can't ensure that various special situations are considered. Therefore, a logarithm that can randomly generate data in different situations comes in handy.

Logarithm, in short, is a combination of an absolutely correct method and a randomizer that can produce a large number of random samples. See here, some children's shoes have questions. Now that we know the absolutely correct method, wouldn't it be better to use this method directly?

Please note that the pursuit of the algorithm is not to solve the problem, but to solve the problem efficiently. For the sorting of an array, if the time complexity required in the written test is O(NlogN), but you write a bubble sorting algorithm and hand it in, OJ will prompt:

Time Limit Exceeded

In the logarithm, the absolutely correct algorithm we require is not limited by time and space complexity, and the only requirement is to ensure absolute correctness. Because only when it is absolutely correct can we find out where our code is wrong through the comparison of samples.

Related concepts

1. There is a method you want to measure a;
2. Implement an absolutely correct but less complex method b;
3. Implement a random sample generator;
4. The method of implementing the comparison algorithm a and b;
5. Compare method a and method b several times to verify whether method a is correct;
6. If there is a sample that makes the comparison error, print which method of sample analysis is wrong;
7. When the number of samples is large, the comparison test is still correct, and it can be determined that method a has been correct.

The following points should be noted:

• The randomly generated samples should be small data sets, but multiple (10w +) comparisons should be made. Small data sets are convenient for comparative analysis, and multiple comparisons should cover all random situations.
• The algorithm b should be correct.

Example

Logarithm of bubble sort:

1. Method to be tested

   public static void bubbleSort(int[] arr){
       if (arr==null || arr.length < 2){
           return;
       }     
       for (int end = arr.length - 1;end>0; end--){
           for (int i = 0; i < end; i++){
               if(arr[i]>arr[i+1]){
                   swap(arr, i, i+1);
               }
           }
                   
       }
   }

2. Implement an absolutely correct method b that can reduce the complexity

   // You can test directly with some library functions
   public static void rightMethod(int[] arr){
       Arrays.sort(arr);
   }

3. Implement a random sample generator

   // Random number generator
   public static int[] generateRandomArray(int size, int value){
       //Math.random() -> double [0,1)
       //(int) ((size + 1) * Math. Random()) - > [0, size] integer
       // Generate an array with random length [0, size]
       int[] arr = new int[(int) ((size+1) * Math.random())];
       for (int i = 0; i < arr.length; i++){
           // Subtract another random number from one random number to generate a random number of [- value, value]
           arr[i] = (int) ((value+1) * Math.random()) - (int) (value * Math.random());
       }
       return arr;
   }

4. Method for realizing comparison

   // Determine whether two arrays are equal
   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;
   }

5. Compare method a and method b several times
6. If there is a sample that makes this comparison wrong, print the sample. Where is the wrong analysis method

7. When the number of samples is enough and the comparison test is still correct, it can be determined that the method a we write is correct

   public static void main(String[] args) {
       int testTime = 500000;
       int size = 10;
       int value = 100;
       boolean succeed = true;
       for (int i = 0; i < testTime; i++){
           int[] arr1 = generateRandomArray(size, value);
           int[] arr2 = copyArray(arr1);
           int[] arr3 = copyArray(arr1);
           bubbleSort(arr1);
           rightMethod(arr2);
           if (!isEqual(arr1, arr2)){
               succeed = false;
               printArray(arr3);
               break;
           }
       }
       System.out.println(succeed ? "Nice!" : "error----");
       int[] arr = generateRandomArray(size, value);
       printArray(arr);
       bubbleSort(arr);
       printArray(arr);
   }

Tips

Many children's shoes memorize some codes written in small books before the written test, and then rush to battle. The correctness of the algorithm written depends entirely on OJ's judgment. When the program card makes an error at an array sample of 2000 lines, it's completely stupid This T meow asks me how to debug and analyze. The small partners with logarithms are different. Because they use small samples, they also conduct analysis in case of errors. And many tests have been carried out to ensure that all special cases are covered. Therefore, before the written examination, we can prepare some logarithm templates, such as logarithm of array sorting, logarithm of linked list, etc.