一、前情回顾
👉传送门: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;
}
}
新建一个ArrayGenerator类，专门用于生成数组
数组生成中的方法采用静态方法，且用户无需生成一个ArrayGenerator的对象，因此将构造函数设置为私有
此处主要用于测试前面的线性查找算法的性能，所以生成的数组中的元素顺序存放，范围[ 0... n − 1 ] [0...n-1][0...n−1]，其中n是由用户进行指定的
2.使用测试用例
public class LinearSearchGenerator {
private LinearSearchGenerator(){}
public static 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 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.2 不同规模的测试用例的用时比较
public class LinearSearchGenerator {
private LinearSearchGenerator() {
}
public static 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的增长相应的算法的性能增长的趋势其实就是这个意思
