JavaScript 中的斐波那契数列
在给定的问题陈述中,我们被要求借助 JavaScript 功能创建一个斐波那契数列。在 JavaScript 中,我们可以借助递归或使用 for 循环来解决这个问题。
什么是斐波那契数列?
让我们了解 JavaScript 中斐波那契数列的工作原理。
众所周知,斐波那契数列是一个数字序列,其中每个数字都是前面两个数字的总和。该系列从 0 和 1 开始。该系列中的下一个数字是 1 (0 + 1),然后是 2 (1 + 1)、3 (1 + 2)……以此类推。
上述问题的逻辑
实现斐波那契数列的最简单方法是借助递归方法。
让我们来理解给定问题的逻辑。JavaScript 中斐波那契数列的递归方法将问题分解为更小的子问题。它首先检查输入数字是否小于或等于 1。如果等于 1,则返回该数字,否则不返回。然后,它将通过递归调用以 n-1 和 n-2 作为参数定义的函数并将结果相加来计算第 n 个斐波那契数。
算法
步骤 1 - 声明一个数字直到得到斐波那契数列或生成 n 项的序列。在这里我们将看到这两种实现。
步骤 2 - 将 n1 和 n2 数字分别声明为 0 和 1。并将 nextDigit 数字定义为空。此处 nextDigit 将是两个数字 n1 和 n2 的总和。
步骤 3 − 此步骤将计算并确定我们对两个代码使用的方法。如果我们想要输出达到某个数字,那么我们将使用 while 循环,此循环将运行直到条件 nextDigit 小于或等于该数字,然后打印序列。如果我们想要输出达到 n 项,那么我们将使用 for 循环来迭代给定输入数字的长度。
步骤 4 − 现在转到第三步,根据需要打印斐波那契数列。
示例
// 代码生成达到某个数字的斐波那契数列 const number = 13; let n1 = 0, n2 = 1, nextDigit; console.log('斐波那契数列如下:'); // 最初打印 0 和 1 console.log(n1); console.log(n2); // 将两个连续的数字相加 nextDigit = n1 + n2; while (nextDigit <= number) { // 打印下一个数字 console.log(nextDigit); n1 = n2; n2 = nextDigit; nextDigit = n1 + n2; }
输出
Fibonacci Sequence is as follows: 0 1 1 2 3 5 8 13
示例
// 生成最多 n 项的斐波那契数列的代码 const number = 8; let n1 = 0, n2 = 1, nextDigit; console.log('斐波那契数列如下:'); //初始化 for 循环 for (let i = 1; i <= number; i++) { console.log(n1); nextDigit = n1 + n2; n1 = n2; n2 = nextDigit; }
输出
斐波那契数列 i 如下: 0 1 1 2 3
时间复杂度
生成某个数字的时间复杂度为 O(log n)。因为代码使用 while 循环来获取给定数字的序列。此循环持续到 nextDigit 大于输入数字,此时 while 循环将终止。由于 while 循环迭代 n 次底数为 2 的对数,因此此代码的复杂度为 O(log n)。第一个代码的空间复杂度为 O(1),因为所需空间不取决于输入大小。
第二种方法的时间复杂度为 O(n),n 是序列中的项数。此代码块使用 for 循环迭代从 1 到输入数字的所有数字范围。由于循环运行 n 次,因此复杂度为 O(n)。
第二种方法的空间复杂度也是 O(n),因为它在循环的每一步都存储值 n1 和 n2。由于这些数字所需的内存是恒定的,并且不取决于输入大小。因此在这种情况下,我们忽略了对空间复杂度的分析。
结论
在此代码中,我们实现了两种代码或算法。第一个代码给出输出以打印斐波那契数列直到某个数字。第二个代码返回 n 项的输出。我们得出结论,第一种方法和第二种方法的时间复杂度分别为 O(log n) 和 O(n)。两种代码的空间复杂度均为 O1)。