时间戳

首页 > 解决方案 > 我正在使用斐波那契数，其中第 n 个数的“n”为 5-6 位。我怎样才能减少执行所需的时间？

java - 我正在使用斐波那契数，其中第 n 个数的“n”为 5-6 位。我怎样才能减少执行所需的时间？

问题描述

在这个特定的问题中，我要做的是找到斐波那契数，将它们平方，然后找到这些平方数的总和。在长数据类型的范围限制之前，这很好。

这是我到目前为止所拥有的......在注意到 long 的范围无法处理大的斐波那契数之后，我切换到 BigInteger，这起到了作用，但时间复杂度呈指数增长。因为我需要保留大部分数字，所以我需要为这些数字创建一个数组来存储它们。

import java.util.*;
import java.math.*;
public class FibonacciSumSquares {
    private static BigInteger getFibonacciSumSquares(int n) {

        if (n <= 1)
            return BigInteger.valueOf(n);

        BigInteger sum = BigInteger.valueOf(0);
        BigInteger a[] = new BigInteger[n];
        a[0] = a[1] = BigInteger.ONE;
        for (int i = 2; i < n; i++) {
            a[i] = a[i - 1].add(a[i - 2]);
            a[i] = a[i].pow(2);
            sum = sum.add(a[i]);
        }
        return sum;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        System.out.println(getFibonacciSumSquares(n));
    }
}

接受第一个答案后，我对代码片段进行了一些压力测试，所需的更正是代码中的“=”符号。希望有帮助。有关更多详细信息，请参阅答案的评论。

标签： java

解决方案

BigInteger 的运行速度比 java 原始类型慢，所以在长距离范围内使用原始类型。这是我的代码和结果：

public class FibonacciSumSquares {
private static BigInteger getFibonacciSumSquares(int n) {
    if (n <= 1)
        return BigInteger.valueOf(n);
    BigInteger sum = BigInteger.ZERO;
    long last = 1, lastTwo = 1, current = 0;
    BigInteger lastBigInteger = BigInteger.ONE;
    BigInteger lastTwoBigInteger = BigInteger.ONE;
    BigInteger currentBigInteger;
    boolean isUsePrimary = true;

    for (int i = 2; i <= n; i++) {
        if (isUsePrimary) {
            current = last + lastTwo;
            current = current * current;
            if (current > (last + lastTwo)) {
                lastTwo = last;
                last = current;
                sum = sum.add(BigInteger.valueOf(current));
            } else {
                isUsePrimary = false;
                lastTwoBigInteger = BigInteger.valueOf(lastTwo);
                lastBigInteger = BigInteger.valueOf(last);
                currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
                currentBigInteger = currentBigInteger.pow(2);

                sum = sum.add(currentBigInteger);
            }
        } else {
            currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
            currentBigInteger = currentBigInteger.pow(2);
            sum = sum.add(currentBigInteger);
        }
    }
    return sum;

}

public static void main(String[] args) {
    long start = System.currentTimeMillis();
    System.out.println(getFibonacciSumSquares(10000));
    System.out.println("used time(ms): " + (System.currentTimeMillis() - start));
    /**
     * On: MacBook Pro (Retina, 15-inch, Mid 2014)
     *
     * n = 10000
     * 811453295998950457153326378602357232029212
     * used time(ms): 24
     *
     * n = 20000
     * 1623556274380606238932066737816445867589212
     * used time(ms): 32
     *
     * n = 999999
     * 81209566945485034687670444066761210743605656
     * used time(ms): 368
     */
}

}

推荐阅读