扎实打牢数据结构算法根基，从此不怕算法面试系列之week01 02-09 测试算法时间复杂度性能的方式方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了扎实打牢数据结构算法根基，从此不怕算法面试系列之week01 02-09 测试算法时间复杂度性能的方式方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、数组生成器

测试算法性能肯定不能自己手动声明创建数组了，在现代计算机上，对于O(n)级别的算法，都需要10W级别以上的数据才能看到性能，我们肯定不能手动声明10W个元素的数组吧？

所以，创建数组生成器。
这里，自己创建一个数组生成器——ArrayGenerator。

package com.mosesmin.datastructure.week01.chap02;

/**
 * @Misson&Goal 代码以交朋友、传福音
 * @ClassName ArrayGenerator
 * @Description TODO 数组生成器
 * @Author MosesMin
 * @Date 2023/4/14
 * @Version 1.0
 */
public class ArrayGenerator {
    private ArrayGenerator() {}
    public static Integer[] generatedOrderedArray(int n){
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++)
            arr[i] = i;
        return arr;
    }
}

2、使用数组生成器进行测试

详细代码如注释：
package com.mosesmin.datastructure.week01.chap02;

/**
 * @Misson&Goal 代码以交朋友、传福音
 * @ClassName LinearSearch03
 * @Description TODO
 * @Author MosesMin
 * @Date 2023/4/14
 * @Version 1.0
 */
public class LinearSearch09 {

    private LinearSearch09(){}
    public static <E> int search(E [] data,E target){
        for (int i = 0; i < data.length; i++)
            if (data[i].equals(target))
                return i;
        return -1;
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] data = ArrayGenerator.generatedOrderedArray(n);// 10w的数据规模
        long startTime = System.nanoTime();//单位是纳秒  纳秒-微妙-毫秒-秒 差距都是1000倍
        for (int k=0;k<100;k++)
            LinearSearch09.search(data,n);//这里为了验证最差的情况，就传一个找不到的目标元素100000
        long endTime = System.nanoTime();
        double time = (endTime-startTime)/(1000*1000*1000.0);// 最后1000.0，因为我们希望结果是个浮点数
        System.out.println(time + " s");
    }


}

10W的数据规模，运行一次，在我的电脑（CPU为：Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz 3.20 GHz）运行时间约为0.0027秒，即2.7毫秒。
3毫秒，可能不够稳定，不一定是线性查找法运行的时间结果，因为操作系统也在运行，我们可以再试下使用更大的数据，比如使用100W的数据规模，看看它们运行
的时间差是否为10倍左右。

运行结果：
10W数据规模：

我们看到100W的运行结果约为6.6毫秒；几毫秒的运行结果还是不够稳。

100W数据规模：

我们再试下1000W的数据规模。
我们看到1000w约为26毫秒；
注：
对于一般的计算机而言，1000W的数据规模已经是个够量的规模了。
1000W数据规模：

我们还可以看一下1亿的规模，但是运行1亿的数据规模时，我的电脑运行了很久，将近20s时间，最终显示结果约为182毫秒。
为什么实际上运行了20s时间呢？
因为对于一般的计算机来说，开1亿个整型空间，尤其时1亿个连续的整型空间时需要一些时间的，特别是我的电脑配置不太高，i5的4代cpu（Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz 3.20 GHz）。

1亿数据规模：

如果我们希望得到的时间更长一些，一个简单方法是，多做几次，这里，我们就用100W的数据规模，然后测试100次。
100W的规模，执行100次，约为218毫秒。

100W数据规模运行100次：

3、一些测试优化

1、优化一下输出log
主要改动的语句为：

System.out.println("数据规模n为："+n+"，运行次数："+ num +"次，运行时间为：" + time + " s.");

优化后的代码如下：
package com.mosesmin.datastructure.week01.chap02;

/**
 * @Misson&Goal 代码以交朋友、传福音
 * @ClassName LinearSearch03
 * @Description TODO
 * @Author MosesMin
 * @Date 2023/4/14
 * @Version 1.0
 */
public class LinearSearch09 {

    private LinearSearch09(){}
    public static <E> int search(E [] data,E target){
        for (int i = 0; i < data.length; i++)
            if (data[i].equals(target))
                return i;
        return -1;
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] data = ArrayGenerator.generatedOrderedArray(n);// 10w的数据规模
        long startTime = System.nanoTime();//单位是纳秒  纳秒-微妙-毫秒-秒 差距都是1000倍
        int num = 100;
        for (int k=0;k<num;k++)
            LinearSearch09.search(data,n);//这里为了验证最差的情况，就传一个找不到的目标元素100000
        long endTime = System.nanoTime();
        double time = (endTime-startTime)/(1000*1000*1000.0);// 最后1000.0，因为我们希望结果是个浮点数
        System.out.println("数据规模n为："+n+"，运行次数："+ num +"次，运行时间为：" + time + " s.");
    }
}

2、创建数据规模数组，利用循环一次测试多个数据规模

int [] dataSize = {100000,1000000,10000000};
for (int n:dataSize) {
……
}

添加数据规模数组后的代码如下：

package com.mosesmin.datastructure.week01.chap02;

/**
 * @Misson&Goal 代码以交朋友、传福音
 * @ClassName LinearSearch03
 * @Description TODO
 * @Author MosesMin
 * @Date 2023/4/14
 * @Version 1.0
 */
public class LinearSearch09 {

    private LinearSearch09(){}
    public static <E> int search(E [] data,E target){
        for (int i = 0; i < data.length; i++)
            if (data[i].equals(target))
                return i;
        return -1;
    }

    public static void main(String[] args) {
        int [] dataSize = {100000,1000000,10000000};
        for (int n:dataSize) {
            Integer[] data = ArrayGenerator.generatedOrderedArray(n);// 10w的数据规模
            long startTime = System.nanoTime();//单位是纳秒  纳秒-微妙-毫秒-秒 差距都是1000倍
            int num = 100;
            for (int k=0;k<num;k++)
                LinearSearch09.search(data,n);//这里为了验证最差的情况，就传一个找不到的目标元素100000
            long endTime = System.nanoTime();
            double time = (endTime-startTime)/(1000*1000*1000.0);// 最后1000.0，因为我们希望结果是个浮点数
            System.out.println("数据规模n为："+n+"，运行次数："+ num +"次，运行时间为：" + time + " s.");
        }
    }
}

创建一个数据规模数组，循环执行，可以看是10W、100W、1000W的运行时间差异确实约为10倍的差距。

ok，到这里，我们的测试方法讲解结束了，后续我们都可以用这样的方式来对不同的算法做测试。文章来源地址https://www.toymoban.com/news/detail-419713.html

到了这里，关于扎实打牢数据结构算法根基，从此不怕算法面试系列之week01 02-09 测试算法时间复杂度性能的方式方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！