Hyperfactorial in Java

一个数的超级阶乘是通过将从 1 到该数的连续数字乘以其幂来计算的。

数学上，

因此，

H(1) = 1 ^ 1 = 1

H(2) = 1 ^ 1 × 2 ^ 2 = 1 × 4 = 4

H(3) = 1 ^ 1 × 2 ^ 2 × 3 ^ 3 = 1 × 4 × 27 = 108

H(4) = 1 ^ 1 × 2 ^ 2 × 3 ^ 3 × 4 ^ 4 = 1 × 4 × 27 × 256 = 27648

H(5) = 1 ^ 1 × 2 ^ 2 × 3 ^ 3 × 4 ^ 4 × 5 ^ 5 = 1 × 4 × 27 × 256 × 3125 = 86400000

Java 计算超级阶乘数的程序

以下程序使用数学公式来计算超级阶乘数。

文件名： HyperFactorialNumber.java

输出

The first 5 HyperFactorial numbers are: 
1 4 108 27648 86400000

为了计算每个超级阶乘数，上述程序需要 O(n ^ 2) 的时间。我们可以进行优化以降低时间复杂度。请看以下程序。

文件名： HyperFactorialNumber1.java

输出

The first 5 HyperFactorial numbers are: 
1 4 108 27648 86400000

findPow() 方法的时间复杂度为 O(log(n))，该方法被一个时间复杂度为 O(n) 的 for 循环调用。因此，总时间复杂度为 O(nlog(n))，优于之前的代码。

使用递归计算超级阶乘数

也可以使用递归来计算超级阶乘数。计算超级阶乘数的递归公式是：

H(1) = 1

H(p) = H(p - 1) × p ^ p，其中 p >= 2

因此，

H(2) = H(2 - 1) × 2 ^ 2 = H(1) × 4 = 1 × 4 = 4

H(3) = H(3 - 1) × 3 ^ 3 = H(2) × 27 = 4 × 27 = 108

H(4) = H(4 - 1) × 4 ^ 4 = H(3) × 256 = 108 × 256 = 27648

H(5) = H(5 - 1) × 5 ^ 5 = H(4) × 15625 = 27648 × 15625 = 86400000

让我们将上述递归公式翻译成 Java 代码。

文件名： HyperFactorialNumber2.java

输出

The first 5 HyperFactorial numbers are: 
1 4 108 27648 86400000