我正在使用线性搜索算法，从该算法的理论来看，它的时间复杂度为 O(n)。现在我必须使用实际代码来证明这一点，并创建一个图表来证明该算法实际上是 O(n)。但有些实际结果根本没有显示这一点。
这是我使用的编码方法：
- 我有一个循环，它根据循环号动态创建一个数组。
- 然后我用数字随机填充这个数组。
- 然后我实现线性搜索算法。现在在算法运行之前，我记下时间，一旦找到我要搜索的值，我就会停止时钟并保存时间，并在循环结束时将值写入文本文件。
- 然后我将文本文件导入 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;
}
这是结果图。我不应该得到一个直线图吗？
