Странные результаты времени при измерении производительности двоичного и линейного поиска

Question

Следующая программа работает как ожидалось / требуется, но время выполнения не имело смысла.

В моем классе Data Structures нам пришлось написать программу для проверки эффективности алгоритма. Возьмите массив и заполните его случайными числами, а затем верните количество всех элементов, равное другому случайному числу. Мы должны были сделать это, используя линейный поиск, а затем бинарный поиск, с массивом из 100 элементов, затем 1k, затем 10k, затем 100k и 1m элементов. Большинство из нас в классе заметили, что при линейном поиске 10 тыс. Элементов требуется больше времени, чем 100 тыс. Элементов.

Мой включил цикл, в котором после завершения обоих поисков массив был расширен и удален, так что это не проблема с кодом. Это происходило только при таком размере, и не имело значения, были ли запущены другие программы или нет. Мы решили, что это потому, что время обработки каждого поиска шло так быстро, что у системы не было времени использовать больше ресурсов, но когда она приблизилась к 10 тыс., Она начала использовать больше, что привело к сокращению времени поиска на 100 тыс. Есть ли другие возможности?

package cmsc350;
/**
 * TestExecutionTime - Create two int arrays and fill with random numbers, create
 * random integer.  Search first array for values less than single integer, calculate
 * time to run, output "hits" and run time.  Scan both arrays for common values,
 * calculate time to run, output "hits" and run time.  Repeat 10 times, calculate
 * average run times.  After 10 runs, increase array size by 10x and repeat.
 * @author Rickie
 */
public class TestExecutionTime {
    int[] array1 = new int[100];
    int[] array2 = new int[100];
    //Create array for storing time, storing average time
    long[][] timeArray = new long[50][2];
    long[][] average = new long[5][2];
    int value;


/**
 * Main method - Initialize all arrays, increase array size as needed, call
 * required methods and calculate run time for each pass.
 */
public void runApp(){
    int arrayLength = 100;
    int resultCount;
    long startTime, endTime;
    int counter = 0;
    //Initialize average time array
    for(counter = 0; counter < 5; counter++){
        average[counter][0]=0;
        average[counter][1]=0;
    }
    //Expand array size by 10x after ten passes, call average time method
    for (counter = 0; counter < 50; counter++){
        if (counter%10 == 0 && counter > 0 ){
            System.out.println("Calling ave");
            aveTime(counter);
            arrayLength = (100*((int)Math.pow(10,(counter/10))));
            array1 = new int[arrayLength];
            array2 = new int[arrayLength];
        }
        //Fill arrays and single integer with random numbers between 1 and 99999
        for(int n = 0; n < arrayLength; n++)
            array1[n] = (1 + (int)(Math.random() * 99999));
        for(int k = 0; k < arrayLength; k++)
            array2[k] =(1 + (int)(Math.random() * 99999));
        value = 1 + (int)(Math.random() * 99999);
        //Display pass count and array length
        System.out.print(counter +1+ " " + array1.length + ":  ");
        //Get time, call less than method, get time
        startTime = System.nanoTime();
        resultCount = nbLessThan(array1, value);
        endTime = System.nanoTime();
        //Calculate run time, store in time array, display hits and run time
        timeArray[counter][0] = endTime-startTime;
        System.out.print(resultCount + " " + (timeArray[counter][0]) + " ns   ");
        //Get time, call common value method, get time
        startTime = System.currentTimeMillis();
        resultCount = nbCommonValues(array1, array2);
        endTime = System.currentTimeMillis();
        //Calculate run time, store in time array, display hits and run time
        timeArray[counter][1] = endTime-startTime;
        System.out.println(resultCount + " " + (timeArray[counter][1]) + " ms");
        }
    //Call average time method for final ten passes.
    aveTime(counter);
    }

/**
 * Calculate average time for 10 runs, display average times
 * @param start - int value used for start and end point of the for loop
 */
private void aveTime(int start){
    int index = start/10 - 1;
    for(int counter = start-10; counter < start; counter++){
        average[index][0] =average[index][0]+ (timeArray[counter][0]);
        average[index][1] =average[index][1]+ (timeArray[counter][1]);
    }
    average[index][0] = average[index][0]/10;
    average[index][1] = average[index][1]/10;
    System.out.println("Ave " + array1.length + ": " + average[index][0] + " " + average[index][1]);
}

/**
 * Scan array for elements less than value
 * @param array
 * @param value
 * @return int count - Number of terms in array less than int value
 */
private int nbLessThan(int[] array, int value){
    int count = 0;
    for (int n = 0; n < array.length; n++){
        if (value > array[n])
            count++;
    }
    return count;
}

/**
 * Scan arrays for common elements, count duplicates
 * @param array1
 * @param array2
 * @return int count - Number of common terms between arrays
 */
private int nbCommonValues(int[] array1, int[]array2){
    int count = 0;
    for(int n = 0; n < array1.length; n++){
        for (int k=0; k < array2.length; k++){
            if(array1[n]==array2[k])
                count++;
        }
    }
    return count;
}

}