一、前情回顾
👉传送门:1 详解线性查找法
👉传送门:2 线性查找的优化
👉传送门:3 线性查找的测试
👉传送门:4 循环不变量与复杂度分析
👉传送门:5 常见的时间复杂度
二、算法性能测试
Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};
我们对于之前的线性查找的算法，只是使用了一个含有8个元素的data数组进行测试，这个数组规模太小，在现代计算机上，对于O ( n ) O(n)O(n)这个级别的复杂度，需要一定规模的数据才能看到相应的性能
1.生成测试用例
//作用：为我们生成一个数组， public class ArrayGenerator { // 用户无需生成一个ArrayGenerator的对象，因此将构造函数设置为私有 private ArrayGenerator(){} //使用静态方法 //生成一个数组，数组中的元素是顺序存放 public static Integer[] generateOrderedArray(int n){ //对线性查找进行测试，所以生成的数组中的元素就是[0...n-1] //其中n的大小是变化的，是用户进行输入指定 Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) { arr[i] = i; } return arr; } } return arr; } }
新建一个ArrayGenerator类，专门用于生成数组
数组生成中的方法采用静态方法，且用户无需生成一个ArrayGenerator的对象，因此将构造函数设置为私有
此处主要用于测试前面的线性查找算法的性能，所以生成的数组中的元素顺序存放，范围[ 0... n − 1 ] [0...n-1][0...n−1]，其中n是由用户进行指定的
2.使用测试用例
public class LinearSearchGenerator { private LinearSearchGenerator(){} public static <E> int search(E[] data, E target) { for (int i = 0; i < data.length; i++) { if (data[i] == target) return i; //如果找到目标，返回对应的索引值 } return -1; //如果没有找到目标，返回-1 } public static void main(String[] args) { //准备用于查找的数组，数组中有100000个元素 Integer[] data = ArrayGenerator.generateOrderedArray(100000); int res = LinearSearchGenerator.search(data, 100000); System.out.println(res); //输出res } }
data数组直接使用ArrayGenerator.generateOrderedArray()生成
首次传入的参数为100000，并且将查找的target值设为100000
很明显，在一个元素个数只有100000的数组中，且数组的元素是顺序存放的[0…100000)，查询是否有100000这个数的结果一定是-1
2.1 检验测试用例的用时
为了检验出对于这次查询，这次的函数调用具体消耗了多少时间，我们可以使用Java为我们提供的nanoTime()方法做一个计时
public class LinearSearchGenerator { private LinearSearchGenerator(){} public static <E> int search(E[] data, E target) { for (int i = 0; i < data.length; i++) { if (data[i] == target) return i; //如果找到目标，返回对应的索引值 } return -1; //如果没有找到目标，返回-1 } public static void main(String[] args) { int n = 100000; //准备用于查找的数组，数组中有100000个元素 Integer[] data = ArrayGenerator.generateOrderedArray(n); //nanoTime()方法返回的其实是一个时间戳， // 是一个长整型，当前用纳秒计算的时间戳 long startTime = System.nanoTime(); int res = LinearSearchGenerator.search(data, n); System.out.println(res); //输出res long endTime = System.nanoTime(); //endTime - startTime的值就是两个时间戳之间的线性查找所用的时间，单位是纳秒 //纳秒与秒之间是10^9 //对于结果可以是一个浮点数，所以除以1000000000.0 double time = (endTime - startTime) / 1000000000.0; System.out.println(time + " s"); } }
nanoTime()方法返回的其实是一个时间戳，用纳秒计算
在线性查找算法前使用一次，在线性查找算法结束后使用一次
endTime - startTime的值就是两个时间戳之间的线性查找所用的时间，单位是纳秒
结果如下：
消耗时间也与硬件有关，所以时间不一定相同
2.1 不同规模的测试用例的用时比较
public class LinearSearchGenerator { private LinearSearchGenerator() { } public static <E> int search(E[] data, E target) { for (int i = 0; i < data.length; i++) { if (data[i] == target) return i; //如果找到目标，返回对应的索引值 } return -1; //如果没有找到目标，返回-1 } public static void main(String[] args) { //不同规模的数据 int[] dataSize = {1000000, 10000000}; for (int n : dataSize) { //准备用于查找的数组 Integer[] data = ArrayGenerator.generateOrderedArray(n); //nanoTime()方法返回的其实是一个时间戳， // 是一个长整型，当前用纳秒计算的话时间戳 long startTime = System.nanoTime(); //对于每个规模的数据，可以通过增加查找次数来达到扩大时间规模的目的 /*因为直接进行查找特别大的规模的数据，比如1亿个数据， 尤其我们需要的是连续空间，在一般的计算机上可能也会费一点劲， 我们通过多做几回，对100万个数据进行100次查找，时间也会相对稳定一些 */ for (int k = 0; k < 100; k++) { LinearSearchGenerator.search(data, n); } long endTime = System.nanoTime(); //endTime - startTime的值就是两个时间戳之间的线性查找所用的时间，单位是纳秒 //纳秒与秒之间是10^9 //对于结果可以是一个浮点数，所以除以1000000000.0 double time = (endTime - startTime) / 1000000000.0; System.out.println("n = " + n + ", 100runs: " + time + " s"); } } }
直接将不同规模的数据存放在数组中
int[] dataSize = {1000000, 10000000};
对于每个规模的数据，可以通过增加查找次数来达到扩大时间规模的目的
因为直接进行查找特别大的规模的数据，比如1亿个数据，尤其我们需要的是连续空间，在一般的计算机上可能也会费一点劲，我们通过多做几回，对100万个数据进行100次查找，时间也会相对稳定一些
并且多次测量就有多组数据，可以进行统计分析，计算平均值、标准差等
for (int k = 0; k < 100; k++) { LinearSearchGenerator.search(data, n); }
对于1000000和10000000这两个规模的数据，分别执行查找100次，最后的结果如下：
消耗时间也与硬件有关，所以每次时间都不相同
从运行结果中，可以看到，对于100万级别的数据，进行100次的查询，大概是0.13s的时间，对于1000万级别，大概是0.7s的时间
0.7大概是0.13的5倍(其实有时候是6倍以上甚至10倍，这与计算机的性能有关)，而我们第一次的数据规模是第二次的10倍
从侧面证明了线性查找法的时间复杂度是O ( n ) O(n)O(n)级别的，时间性能和数据规模之间是线性关系
时间复杂度描述的是随着n的增长相应的算法的性能增长的趋势其实就是这个意思
