时间戳

首页 > 解决方案 > 为什么如果我使用循环作为输入，算法会更慢

java - 为什么如果我使用循环作为输入，算法会更慢

问题描述

我想使用 System.currentTimeMillis() 计算 analizeString() 的执行时间。

public static void main(String[] args) {        
    String myString ="";
    for(int character = 0; character < 50000; character+=10000){
        for(int i = 0; i < character; i++){ 
             myString =+ randomCharacter();
        }           

        long time1 = System.currentTimeMillis();
        analizeString(myString);
        long time2 = System.currentTimeMillis();

        printTimeInFile(time2 - time1);

    }}

在这种情况下，当输入为 40000 时，我发现的时间约为 4 秒。但如果我不使用这样的循环：

public static void main(String[] args) {        
    String myString ="";
    long input = 40000;
    //for(int character = 0; character < 50000; character+=10000){
        for(int i = 0; i < input; i++){ 
             myString =+ randomCharacter();
        }           

        long time1 = System.currentTimeMillis();
        analizeString(myString);
        long time2 = System.currentTimeMillis();

        printTimeInFile(time2 - time1);

    }

时间约为 0.3 秒。

随着循环，程序非常慢。为什么会有这种差异？我的假设是上一次也被添加了。有什么帮助吗？谢谢！

标签： javatime-complexity

解决方案

在第一个示例中，您有 10000 + 20000 + 30000 + 40000 = 100000 次迭代，并且您的方法针对 100000 个字符的字符串运行最后一次迭代。

  • 第一次迭代你有 10 000 个字符的时间
  • 第二次迭代你有 30 000 (10 000 + 20 000) 个字符的时间
  • 第三次迭代你有 60 000 (30 000 + 30 000) 个字符的时间
  • 第四次（最后一次）迭代你有 100 000（60 000 + 40 000）个字符的时间

在第二个示例中，您有一个 40000 个字符的字符串。这就是为什么时间不同的原因。

检查您的 analizeString() 方法，将字符串增加 2.5 倍，您的时间增加超过 13 倍（4 秒 / 0,3 秒）

推荐阅读