Java-算法分析篇

程序员文章站 2022-06-03 15:54:40

...

随着使用计算机的经验的增长，人们在使用计算机解决困难问题或是处理大量数据时将不可避免地参数疑问：
1.我的程序会运行多长时间？
2.为什么我的程序耗尽了所以内存？

问题

下面的ThreeSum程序，输入数据的规模N和程序运行时间T有什么关系？

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class ThreeSum {
	public static int count(int[] a)
	{
		//统计和为0的元组的数量
		int N=a.length;
		int cnt=0;
		for(int i=0;i<N;i++)
			for(int j=i+1;j<N;j++)
				for(int k=j+1;k<N;k++)
					if(a[i]+a[j]+a[k]==0)
						cnt++;
		return cnt;
	}
	
	public static void main(String[] args)
	{
		@SuppressWarnings("deprecation")
		int[] a=In.readInts(args[0]);
		StdOut.println(count(a));
	}
}

一般情况下，我们可以使用以下测试程序运行时间：
Java-算法分析篇

public class Stopwatch { 

    private final long start;
    
    public Stopwatch() {
        start = System.currentTimeMillis();
    } 
    
    public double elapsedTime() {
        long now = System.currentTimeMillis();
        return (now - start) / 1000.0;
    }
    
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        // sum of square roots of integers from 1 to n using Math.sqrt(x).
        Stopwatch timer1 = new Stopwatch();
        double sum1 = 0.0;
        for (int i = 1; i <= n; i++)
         {
            sum1 += Math.sqrt(i);
        }
        double time1 = timer1.elapsedTime();
        StdOut.printf("%e (%.2f seconds)\n", sum1, time1);
    }
}

Stopwatch类中，elapsedTime()方法能够返回自它创建以来所经过的时间，以秒为单位。

它的实现基于Java系统的currentTimeMillis()方法，该方法能够返回以毫秒计数的当前时间。

它的构造函数保存了当前的时间，并在elapsedTime()方法被调用时再次调用该方法来计算得到对象创建一来经过的时间。

实验数据的分析

由于不同计算机的性能不同，同样的程序在不同计算机上完成的时间也是不同的。
但是：程序在不同计算机上的运行时间之比通常是一个常数。
对于上面的ThreeSum程序，很容易考虑出其运行时间T是问题规模N的三次方函数：
$T(N) =aN^3 .$
也就是从所有数中取出三个数,C(N,3)
$N(N-1)(N-2)/6.$

		for(int i=0;i<N;i++)
			for(int j=i+1;j<N;j++)
				for(int k=j+1;k<N;k++)
					if(a[i]+a[j]+a[k]==0)
						cnt++;

Java-算法分析篇

数学模型

一个程序运行的总时间主要和两点有关：
1.执行每条语句的耗时；
2.执行每条语句的频率。
前者取决于计算机、Java编译器和操作系统，后者取决于程序本身和输入。

近似

$N(N-1)(N-2)/6=N^3/6-N^2/2+N/3.$
随着N的增加，后面的平方项和一次向可以忽略，于是可以用三次项
$N^3/6$
来近似考虑了。
以下是一个可以近似考虑的：
Java-算法分析篇
其判断根据是每条语句的执行频率。
以下是一些增长级别代码实现：

这里面有一个现象：执行最频繁的语句决定了程序执行的总时间：程序的内循环。
且：许多程序的运行时间都只取决于其中的一小部分指令。