java - 时间复杂度理论与线性搜索的实际实验不匹配

Question

我正在使用线性搜索算法，根据该算法的理论，它的时间复杂度为 O(n)。现在我必须使用实际代码来证明这一点，并创建一个图表来证明该算法实际上是 O(n)。但一些实际结果根本没有显示这一点。

这是我使用的编码方法:

1. 我有一个循环，它根据循环编号动态创建一个数组。
2. 然后我用数字随机填充这个数组。
3. 然后我实现线性搜索算法。现在，在算法运行之前，我会记下时间，一旦找到我正在搜索的值，我就会停止时钟并保存时间，并在循环结束时将这些值写入文本文件。
4. 然后我将文本文件导入 excel 并创建一个图表。但结果并不能证实该算法是 O(n) 的事实

这是我的java代码:

 public static void main(String[] args) 
    {
        
        long[] ArrayTimeTaken = new long[10000];
        String Display = "";
        
        //Code that runs the linear search
        for (int i = 2; i < 10000; i++) 
        {
            int[] arrayExperimentTest = new int[i];
            arrayExperimentTest = FillArray(i);
            int ValuetoSearchfor = Math.round(((arrayExperimentTest.length)/2));
            System.out.println(ValuetoSearchfor);
            ArrayTimeTaken[i] = LinearSearch(arrayExperimentTest,ValuetoSearchfor);
            Display = Display+ System.getProperty("line.separator") + ArrayTimeTaken[i]; 
           
        }
        PrintWriter writer;
        try {
            writer = new PrintWriter("C:/Users/Roberto/Desktop/testing.txt", "UTF-8");
            writer.println(Display);
            writer.close();
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (UnsupportedEncodingException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        //ChartCreate(ArrayTimeTaken);  
        System.out.println("Done");
    }

下面是用随机数和线性搜索填充数组的代码:

 //This code simply populates our array with numbers in each of the array positions
    static int[] FillArray(int number)
    {
        int[] ArrayofValues = new int[number];
        for (int i = 0; i < number; i++) 
        {
            Random randomGenerator = new Random();
            boolean flag = true;
            while (flag) 
            {                
                int index = randomGenerator.nextInt(number);
                if (ArrayofValues[index] == 0)
                {
                    ArrayofValues[index] = i;
                    flag = false;
                }
            }
        }
        return ArrayofValues;
    }
    
    //This function does a linear search on an array with integers
    static long LinearSearch(int[] ArraySearch,int ValueFind)
    {
        long TimeTaken = 0;
        long startTime = System.currentTimeMillis();
        System.gc();
        
        for (int i = 0; i < ArraySearch.length; i++) 
        {
            if (ArraySearch[i] == ValueFind) 
            {
                TimeTaken = System.currentTimeMillis() - startTime;
                break;
            }
            
        }
        return TimeTaken;
        
    }

这是结果图。我不应该得到一个直线图吗？

Answer 1

您无法从单次运行中推断出结果。使用类似 Google Caliper 的东西正确地进行微基准测试，这将为您生成各种有用的指标(标准偏差等)，以及许多重要的技术问题(预热 JVM，以便可能优化字节码)。

除了assylias的回答——做IO可能会对你的结果产生巨大的影响。在没有图形 UI 且运行的服务数量最少的操作系统上运行也是一种很好的做法。

阅读Caliper wiki有关微基准测试的最佳实践，请查看 source for examples .

(编辑:对于版本 1.0-beta-1 检查此 branch for examples ，API 正在更改并且 master 与文档不匹配)