Java 中的 Kynea 数

在本节中，我们将学习什么是 Kynea 数，并创建Java 程序来计算Kynea 数。Kynea 数程序经常出现在 Java 编码面试和学术中。

Kynea 数是递归定义的数字，如下所示：

F(k) = 4 x F(k - 1) - 2 ^{k + 1} + 3，其中 F(0) 等于 2。

因此，

对于 k = 1，

F(1) = 4 x F(1 - 1) - 2 ^{1 + 1} + 3 = 4 x F(0) - 2² + 3 = 4 x 2 - 4 + 3 = 8 - 4 + 3 = 4 + 3 = 7

对于 k = 2，,

F(2) = 4 x F(2 - 1) - 2 ^{2 + 1} + 3 = 4 x F(1) - 2³ + 3 = 4 x 7 - 8 + 3 = 28 - 8 + 3 = 20 + 3 = 23

对于 k = 3，,

F(3) = 4 x F(3 - 1) - 2 ^{3 + 1} + 3 = 4 x F(2) - 2⁴ + 3 = 4 x 23 - 16 + 3 = 92 - 16 + 3 = 76 + 3 = 79

对于 k = 4，,

F(4) = 4 x F(4 - 1) - 2 ^{4 + 1} + 3 = 4 x F(3) - 2⁵ + 3 = 4 x 79 - 32 + 3 = 316 - 32 + 3 = 284 + 3 = 287

对于 k = 5，,

F(5) = 4 x F(5 - 1) - 2 ^{5 + 1} + 3 = 4 x F(4) - 2⁶ + 3 = 4 x 287 - 64 + 3 = 1148 - 64 + 3 = 1084 + 3 = 1087

方法：使用递归

上述递归公式可以使用递归轻松实现。请观察以下程序。

文件名： KyneaNumbers.java

输出

The first 10 Kynea Numbers are: 
2 7 23 79 287 1087 4223 16639 66047 263167

复杂度分析：该程序使用递归和快速幂运算。递归直到 k = 0，因此，对于递归，时间复杂度为 O(k)，对于快速幂运算，时间复杂度为 O(log2(k + 1))。因此，该程序的总体时间复杂度为 O(k * log2(k + 1))，其中 k 是必须找到的第 k 个 Kynea 数。该程序不使用任何额外空间，因此空间复杂度为常数，即 O(1)。

方法：使用辅助数组

借助辅助数组，我们可以避免递归以降低时间复杂度。以下程序显示了这一点。

文件名： KyneaNumbers1.java

输出

The first 10 Kynea Numbers are: 
2 7 23 79 287 1087 4223 16639 66047 263167

复杂度分析：程序的 [时间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-time-complexity/) 只在于快速幂运算。因此，程序的[时间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-time-complexity/)为 O(log₂(k + 1)，其中 k 是必须找到的第 k 个 Kynea 数。由于程序使用辅助数组来存储先前计算的结果，因此[空间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-space-complexity/)为 O(n)，其中 n 是必须找到的 Kynea 数的总数。

我们仍然可以降低程序的[空间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-space-complexity/)，因为从递归公式可以明显看出，当前值仅取决于先前计算的值。请观察以下程序。

文件名： KyneaNumbers2.java

输出

The first 10 Kynea Numbers are: 
2 7 23 79 287 1087 4223 16639 66047 263167

复杂度分析：程序的[时间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-time-complexity/)与前一个程序相同。然而，程序的[空间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-space-complexity/)为 O(1)，因为程序不使用任何辅助数组。

方法：使用数学公式

寻找 Kynea 数的数学公式是：

F(k) = 4^k + 2^{k + 1} - 1，对于 k >= 0

因此，

F(0) = 4⁰ + 2^{0 + 1} - 1 = 1 + 2¹ - 1 = 2

F(1) = 4¹ + 2^{1 + 1} - 1 = 4 + 2² - 1 = 4 + 4 - 1 = 7

F(2) = 4² + 2^{2 + 1} - 1 = 4² + 2³ - 1 = 16 + 8 - 1 = 23

F(3) = 4³ + 2^{3 + 1} - 1 = 4³ + 2⁴ - 1 = 64 + 16 - 1 = 79

F(4) = 4⁴ + 2^{4 + 1} - 1 = 4⁴ + 2⁵ - 1 = 256 + 32 - 1 = 287

F(5) = 4⁵ + 2^{5 + 1} - 1 = 4⁵ + 2⁶ - 1 = 1024 + 64 - 1 = 1087

观察使用此数学公式计算 Kynea 数的以下程序。

文件名： KyneaNumbers2.java

输出

The first 10 Kynea Numbers are: 
2 7 23 79 287 1087 4223 16639 66047 263167

复杂度分析：程序的[时间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-time-complexity/)和[空间复杂度](https://www.geeksforgeeks.org/analysis-of-algorithms-space-complexity/)与前一个程序相同。