为什么我的程序有更长的运行时间，而它应该有更短的运行时间？

Question

我有两个程序来计算用户指定的斐波那契数列中的第 n 项。第一个程序是这样的：

import java.util.Scanner;
import java.text.DecimalFormat;
import java.math.BigInteger;
import java.io.BufferedWriter;
import java.io.FileWriter;

public class Fibonacci
{
    // main(String[]) - Bulk of the program
    public static void main(String[] args)
    {
        long lStartTime;
        long lFinishTime;
        long lTotalTime;
        long l;
        long lInput = 0L;
        long lToGoTo = 0L;
        String strInput;
        Scanner keyboard = new Scanner(System.in);
        DecimalFormat df = new DecimalFormat("#,##0");
        BigInteger biNMinusOne = BigInteger.ZERO;
        BigInteger biN = BigInteger.ONE;
        BigInteger biHeld;
        FileWriter fw;
        BufferedWriter bw;

        try
        {
            System.out.print("\nEnter which term of the Fibonacci Sequence you would like: ");
            lInput = keyboard.nextLong();
            lToGoTo = lInput - 1L;
        }
        catch (Exception e)
        {
            System.exit(0);
        }

        lStartTime = System.currentTimeMillis();
        if(lInput != 0)
        {
            for(l = 0; l < lToGoTo; l++)
            {
                biHeld = biNMinusOne.add(biN);
                biNMinusOne = biN;
                biN = biHeld;
                System.out.print(l + "\n");
            }
        }
        else
        {
            biN = BigInteger.ZERO;
        }
        System.out.print(lInput + "\n");
        lFinishTime = System.currentTimeMillis();
        lTotalTime = lFinishTime - lStartTime;
        System.out.print("\nTotal Computation Time: " + lTotalTime + "ms\n");

        try
        {
            fw = new FileWriter("Fibonacci.txt");
            bw = new BufferedWriter(fw);
            bw.write(df.format(biN).toString());
            bw.close();
            System.out.print("\nSee \"Fibonacci.txt\" to see the result.\n");
        }
        catch (Exception e)
        {
            System.out.print("\nError!\n");
        }
    }// End main(String[])
}//end Fibonacci

并通过迭代计算第n项。

我的第二个程序是这样的：

import java.util.Scanner;
import java.text.DecimalFormat;
import java.math.BigInteger;
import java.io.BufferedWriter;
import java.io.FileWriter;

/**
 * Documentation:
 * Fibonacci Identity A^n = n+1 n
 *                          n n-1
 * where for n = 1    A^1 = 1   1
 *                          1   0
 * and/or where n corresponds to the nth Fibonacci term
 * and where if the user inputs n, the n+1 term in the n-1 exponentiation of A will
 * be the requested term
 */
public class Fibonacci
{
    // main(String[]) - Bulk of the program
    public static void main(String[] args)
    {
        long l;
        long lStart;
        long lFinish;
        long lInput = 0L;
        long lTerm = 0L;
        BigInteger biN = BigInteger.ZERO;
        BigInteger[][] rgbiN  = new BigInteger[2][2];
        BigInteger[][] rgbiFibonacci = {{BigInteger.ONE, BigInteger.ONE}, 
                                       {BigInteger.ONE, BigInteger.ZERO}};
        Scanner keyboard = new Scanner(System.in);
        DecimalFormat df = new DecimalFormat("#,##0");
        FileWriter fw;
        BufferedWriter bw;

        try
        {
            System.out.print("\nEnter which term of the Fibonacci Sequence you would like: ");
            lInput = keyboard.nextLong();
            lTerm = lInput - 2;
        }
        catch (Exception e)
        {
            System.exit(0);
        }

        lStart = System.currentTimeMillis();
        rgbiN = rgbiFibonacci;
        if(lTerm != -1)
        {
            for(l = 0; l < lTerm; l++)
            {
                rgbiN = multiplyMatrix(rgbiN);
                System.out.print(l + "\n");
            }
            biN = rgbiN[0][0];
            System.out.print(l + "\n");
        }
        lFinish = System.currentTimeMillis() - lStart;
        System.out.print("\nTotal Computation Time: " + lFinish + "ms\n");

        try
        {
            fw = new FileWriter("Fibonacci.txt");
            bw = new BufferedWriter(fw);
            bw.write(df.format(biN).toString());
            bw.close();
            System.out.print("\nSee \"Fibonacci.txt\" to see the result.\n");
        }
        catch (Exception e)
        {
            System.out.print("\nError!\n");
        }
    }// End main(String[])

    public static BigInteger[][] multiplyMatrix(BigInteger[][] n)
    {
        BigInteger biA;
        BigInteger biB;
        BigInteger biC;
        BigInteger biD;
        BigInteger[][] rgbiN = new BigInteger[2][2];
        BigInteger[][] rgbiFibonacci = {{BigInteger.ONE, BigInteger.ONE}, 
                                       {BigInteger.ONE, BigInteger.ZERO}};
        biA = ((n[0][0].multiply(rgbiFibonacci[0][0])).add(n[0][1].multiply(rgbiFibonacci[1][0])));
        biB = ((n[0][0].multiply(rgbiFibonacci[0][1])).add(n[0][1].multiply(rgbiFibonacci[1][1])));
        biC = ((n[1][0].multiply(rgbiFibonacci[0][0])).add(n[1][1].multiply(rgbiFibonacci[1][0])));
        biD = ((n[1][0].multiply(rgbiFibonacci[0][1])).add(n[1][1].multiply(rgbiFibonacci[1][1])));

        rgbiN[0][0] = biA;
        rgbiN[0][1] = biB;
        rgbiN[1][0] = biC;
        rgbiN[1][1] = biD;

        return (rgbiN);
    }//end multiplyMatrix(int[][], int[][])
}//end Fibonacci

并通过矩阵求幂计算序列。

我遇到的问题是，如果我运行第 n 个学期的第一个程序，我的运行时间比运行第二个程序短对于同一个第 n 个学期；这与我读到的关于矩阵求幂更快的所有内容背道而驰。它的运行时间也比执行矩阵求幂的程序慢 found/compiled/edited 来测试它的运行时间与我自己的相比。我究竟做错了什么？任何一个程序中的任何输入我都会欣喜若狂；但是，我更好奇为什么第二个程序的运行时间大于第一个程序的运行时间。

我感觉我搞砸了，基本上是使用矩阵求幂重新实现迭代方法...

请原谅使用匈牙利符号；这是我在 class 中做的作业的扩展，我被要求使用它。

2015 年 11 月 22 日更新：新代码

public class Fibonacci
{
    // main(String[]) - Bulk of the program
    public static void main(String[] args)
    {
        long lStart;
        long lFinish;
        long lNTerm = 0;
        BigInteger biF;
        Scanner keyboard = new Scanner(System.in);
        DecimalFormat df = new DecimalFormat("#,##0");
        FileWriter fw;
        BufferedWriter bw;

        try
        {
            System.out.print("\nEnter which term of the Fibonacci Sequence you would like: ");
            lNTerm = keyboard.nextLong();
        }
        catch (Exception e)
        {
            System.exit(0);
        }

        lStart = System.currentTimeMillis();
        biF = calculateNumber(lNTerm);
        lFinish = System.currentTimeMillis() - lStart;
        System.out.print("\nTotal Computation Time: " + lFinish + "ms\n");

        try
        {
            fw = new FileWriter("Fibonacci.txt");
            bw = new BufferedWriter(fw);
            bw.write(df.format(biF).toString());
            bw.close();
            System.out.print("\nSee \"Fibonacci.txt\" to see the result.\n");
        }
        catch (Exception e)
        {
            System.out.print("\nError!\n");
        }
    }// End main(String[])

    public static BigInteger calculateNumber(long nTerm)
    {
        BigInteger[][] rgbiA = {{BigInteger.ONE, BigInteger.ONE},
                               {BigInteger.ONE, BigInteger.ZERO}};
        BigInteger rgbiR = BigInteger.ZERO;
        if(nTerm > 0)
        {
            rgbiA = exponential(rgbiA, nTerm-1);
            rgbiR = rgbiA[0][0];
        }   
        return (rgbiR);
    }//end calculateNumber(long)

    public static BigInteger[][] exponential(BigInteger[][] fibonacciMatrix, long nTerm)
    {
        long l;
        BigInteger[][] rgbiFibonacci = {{BigInteger.ONE, BigInteger.ONE},
                                       {BigInteger.ONE, BigInteger.ZERO}};
        for(l = 0; l < nTerm-1; l++)
        {
            rgbiFibonacci = multiplyMatrix(fibonacciMatrix, rgbiFibonacci);
        }
        return (rgbiFibonacci);
    }//end exponential(BigInteger[][], long)

    public static BigInteger[][] multiplyMatrix(BigInteger[][] x, BigInteger[][] y)
    {
        BigInteger biA;
        BigInteger biB;
        BigInteger biC;
        BigInteger biD;
        BigInteger[][] rgbiR = new BigInteger[2][2];

        biA = ((x[0][0].multiply(y[0][0])).add(x[0][1].multiply(y[1][0])));
        biB = ((x[0][0].multiply(y[0][1])).add(x[0][1].multiply(y[1][1])));
        biD = ((x[1][0].multiply(y[0][1])).add(x[1][1].multiply(y[1][1])));

        rgbiR[0][0] = biA;
        rgbiR[0][1] = biB;
        rgbiR[1][0] = biB;
        rgbiR[1][1] = biD;

        return (rgbiR);
    }//end multiplyMatrix(BigInteger[][], BigInteger[][])
}//end Fibonacci

Answer 1

首先，您仍在进行线性运算 — 您的矩阵幂计算是 O(N)。为了获得更好的性能，您需要重新实现幂函数，因此它将是 logarithmic

此外，由于 BigInteger、内存分配、函数调用等操作的复杂性，在较小的 N 值上性能几乎相同。

当 N 足够大时，算法的复杂性仍将超过纯粹的 O(log(N))，因为乘法本身不会在 O(1) 中完成，而是在 [=16] 中完成=]，当l为矩阵元素的长度（位数）时

因此，您的幂函数应如下所示：

public static BigInteger[][] exponential(BigInteger[][] fibonacciMatrix, long nTerm)
{
    long l;
    BigInteger[][] rgbiFibonacci = {{BigInteger.ONE, BigInteger.ZERO},
            {BigInteger.ZERO, BigInteger.ONE}};
    while (nTerm > 0) {
        if (nTerm % 2 == 1) {
            rgbiFibonacci = multiplyMatrix(rgbiFibonacci, fibonacciMatrix);
        }
        fibonacciMatrix = multiplyMatrix(fibonacciMatrix, fibonacciMatrix);
        nTerm /= 2;
    }
    return (rgbiFibonacci);
}//end exponential(BigInteger[][], long)

为什么我的程序有更长的运行时间，而它应该有更短的运行时间？

Why is my program having a longer runtime, when it should have a shorter one?

java

iteration

matrix

fibonacci

exponentiation