1.5.22Erods-renyi模型的倍率实验。开发一个性能测试用例 ，从命令行接受一个int值T并进行T次以下实验：使用练习1.5.17的用例生成随机连接，和我们的开发用例一样使用UnionFind来检查触点的连通性，不断循环直到所有触点均相互连通。对于每个N，0打印出N值和平均所需的连接数以及前后两次运行时间的比值。使用你的程序验证正文中的猜想：quick-find算法和quick-union算法的运行时间是平方级别的，加权quick-union算法则接近线性级别。

答：

public class E1d5d22

{

    public static int countOfQuickFind(int N)

    {

        int Times=0;

        QuickFindUF uf=new QuickFindUF(N);

         while (uf.count()>1)

           {

               int p=StdRandom.uniform(N);

               int q=StdRandom.uniform(N);

               Times++;

               uf.union(p,q);

            }//end while

        return Times;

    }

   

     public static int countOfQuickUnion(int N)

    {

        int Times=0;

        QuickUnionUF uf=new QuickUnionUF(N);

        while (uf.count()>1)

           {

               int p=StdRandom.uniform(N);

               int q=StdRandom.uniform(N);

               Times++;

               uf.union(p,q);

            }//end while

        return Times;

    }

    

   public static int countOfWeightedQuickUnion(int N)

    {

        int Times=0;

        WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);

        while (uf.count()>1)

           {

               int p=StdRandom.uniform(N);

               int q=StdRandom.uniform(N);

               Times++;

               uf.union(p,q);

            }//end while

        return Times;

    }

         

   public static void DoubleTestQuickFind(int T)

   {

        int totalConnections=0;

        double lastElapsedTime=0;

        double currentElapsedTime=0;

        StdOut.println("---QuickFind---");

        for(int N=2;N<=Math.pow(2,15);N=N+N)

            {

               Stopwatch timer=new Stopwatch();

               totalConnections=0;

               for (int t=1;t<=T;t++)

                 {

                   totalConnections=totalConnections+countOfQuickFind(N);

                 }

              currentElapsedTime=timer.elapsedTime();

              StdOut.printf("N=%6d  avg Connection=%8d  time=%8.2f   Rate=%5.2f\n",N,totalConnections/T,currentElapsedTime,currentElapsedTime/lastElapsedTime);

              lastElapsedTime=currentElapsedTime;

            }

   }

  

  

   public static void DoubleTestQuickUnion(int T)

   {

        int totalConnections=0;

        double lastElapsedTime=0;

        double currentElapsedTime=0;

        StdOut.println("---QuickUnion---");

        for(int N=2;N<=Math.pow(2,15);N=N+N)

            {

               Stopwatch timer=new Stopwatch();

               totalConnections=0;

               for (int t=1;t<=T;t++)

                 {

                   totalConnections=totalConnections+countOfQuickUnion(N);

                 }

              currentElapsedTime=timer.elapsedTime();

              StdOut.printf("N=%6d  avg Connection=%8d  time=%8.2f   Rate=%5.2f\n",N,totalConnections/T,currentElapsedTime,currentElapsedTime/lastElapsedTime);

              lastElapsedTime=currentElapsedTime;

            }

   }

  

   public static void DoubleTestWeightedQuickUnion(int T)

   {

        int totalConnections=0;

        double lastElapsedTime=0;

        double currentElapsedTime=0;

        StdOut.println("---WeightedQuickUnion---");

        for(int N=2;N<=Math.pow(2,15);N=N+N)

            {

               Stopwatch timer=new Stopwatch();

               totalConnections=0;

               for (int t=1;t<=T;t++)

                 {

                   totalConnections=totalConnections+countOfWeightedQuickUnion(N);

                 }

              currentElapsedTime=timer.elapsedTime();

              StdOut.printf("N=%6d  avg Connection=%8d  time=%8.2f   Rate=%5.2f\n",N,totalConnections/T,currentElapsedTime,currentElapsedTime/lastElapsedTime);

              lastElapsedTime=currentElapsedTime;

            }

   }

  

    public static void main(String[] args)

    {

        int T=Integer.parseInt(args[0]);

       DoubleTestQuickFind(T);

       DoubleTestQuickUnion(T);

       DoubleTestWeightedQuickUnion(T);

    }

}