javaScript 算法基础知识第 4 部分：具有线性时间复杂度 O(n) 和指数时间复杂度 O(2^n) 的递归算法。递归是编程中的关键概念之一。作为一种解决问题的方法，它也被广泛用于数据结构和算法中。它帮助我们将大型复杂问题分解为较小的问题。因此，了解递归的时间复杂性对于理解和提高代码效率至关重要。
对于本系列 JavaScript 算法的第 3 部分，您可以参考以下链接。
第3部分：使用渐近分析推导恒定时间复杂度O(1)
在本文中，我们将介绍递归算法的两个示例及其时间复杂度。
具有线性时间复杂度 O(n) 的递归算法
具有指数时间复杂度 O(2^n) 的递归算法
首先，简要介绍一下递归。
什么是递归？
我们说一个函数是递归函数，如果它直接或间接地调用自己。下面是递归函数的一瞥。
上面的函数是递归函数的一个例子，因为它正在调用自身，但它也是不完整的，因为它会导致无限循环。这是因为该函数没有任何退出条件。但是，这里的关键点是，递归只是从该函数内部调用该函数。
为了非常清楚地说明这一点，让我们看一个简单的例子。
示例问题
创建一个简单的函数来计算输入数字的阶乘。
如果您不知道什么是阶乘，请使用以下输入查看以下函数的行为。
你拿输入数字，乘以这个数字减去1，然后重复相同的操作，直到你达到1。这就是我们计算阶乘的方式。而且，最后，我们可以编写一个函数来做到这一点。
让我们首先看一下非递归方法。因为递归通常(并非总是)只是常规循环的替代方法。因此，让我们尝试首先使用基于循环的方法解决它。
功能(基于循环的方法)
因此，这是一个使用正态循环的阶乘函数。使用这样的循环并不是解决阶乘问题的坏方法。但也存在一种不同的方法来使用递归来解决上述问题。而且，正如您将进一步看到的那样，这种递归将允许我们编写更少的代码，这通常是我们可能想要使用递归的原因之一。
递归解 O(n)
上面的函数是递归的，因为它正在调用自身。在函数中有两件重要的事情要观察，即“if block”和“函数调用”，参数为(n-1)。
我们将 if 块称为“退出条件”或始终返回值的“基本情况”。并且，将“函数调用”作为“递归步骤”。
另一件需要注意的重要事情是，我们在递归步骤中将不同的参数传递给函数调用。因为，如果我们再次调用带有n的函数，我们将不会更改任何内容。我们只会得到一个无限循环。
因此，递归函数应始终具有这两个组件，即“退出条件”和“递归步骤”，否则我们将始终具有无限循环，这将使我们的程序崩溃。
如果满足基本条件，退出条件或基本情况为我们提供了一种退出函数的方法。
而且，递归步骤帮助我们通过对同一函数进行递归调用来计算结果，但输入的大小减小。
这可以表示为函数调用链。就像下面的例子一样，对于一个事实(4)，我们将返回4 * fact(3)，这给了我们3 * 个事实(2)，这将再次给我们2 * 个事实(1)。并且，这最终返回 1，然后将计算的返回值传递给函数调用，从而产生 24。
如何推导递归算法的时间复杂度？
根据渐近分析，我们仍然可以计算上述函数中的操作。因此，每个操作将执行一次，包括 return 语句中的函数调用。
但是，由于我们在 return 语句中有一个函数调用。我们启动一个新的函数调用，因此函数中的所有代码都会再次运行多次，直到满足退出条件。因此，我们可以计算递归函数的函数调用次数。因此，我们可以看到，在上面的示例中，我们得到了 4 个函数调用，函数的阶乘为 4。
在每个函数调用中，我们有一个常量时间，我们的函数中没有任何循环。因此，我们可以将其编写如下。
但是，上述函数调用触发了多个函数调用，即当输入值为n时，n个函数调用。
因此，我们对多个函数调用的时间复杂度将是，
那就是，
这可以写成，
上面的等式最后只是O(n)。而且，这与我们基于循环的解决方案的时间复杂度相同，即线性时间复杂度。
虽然这是递归算法的一个非常简单的示例，但我们也有使用递归的算法，因为它们比替代解决方案产生更好的结果。
递归算法 指数时间复杂度 O(2^n)
在前面的示例中，递归看起来不错，我们通常可以编写更少的代码来解决问题。但是，让我告诉你，递归并不总是最好的解决方案。为了证明这一点，我们将研究斐波那契数列的递归实现。
功能
上述函数是一个斐波那契函数，它启动两个递归函数，触发新的函数调用，直到满足退出条件。解析所有这些函数调用后，结果将冒泡并返回到初始函数。此处的这两个函数中的每一个都将返回一个值，然后将这些值相加。
那么，这种方法有什么问题呢？
这种方法的错误之处在于，当我们调用它时，该函数会构建一个跨多个分支的嵌套递归函数调用树。
这可以在下面的示例图中看到，因为n = 4。
如您所见，我们收到了 9 个函数调用，例如 4 个。如果我们使用基于循环的解决方案来完成它，那么我们只会迭代4次。这不是一个好的解决方案，因为即使对于较小的输入数字(如 4)，函数调用也有大约 9 次执行。
类似地，函数调用呈指数级增长，输入数字从 4 线性增加到 6，如下所示。
如果输入数字进一步增加，情况会变得更糟。
那么这个递归函数的时间复杂度是多少呢？
这绝对不是O(n)，基于循环的解决方案就是这种情况。我们得到了(9)4次处决，(15)次处决5次，(25)执行6次处决。因此，如果我们仅将提供给函数的数量增加 1，则执行次数将呈指数级增长。它不是线性增长的。我们添加的执行次数似乎随着n的增大而增长，并且呈指数级增长。
因此，这里相对较小的上升需要越来越长的时间。事实上，这个时间尺度的复杂性是指数级的。随着n的每个增量，我们向这个递归树添加全新的分支，而不仅仅是一个函数调用。此外，每个分支都由其他分支组成。结果，这很快增加到我们的机器无法处理的体积。因此，对于我们已经有一个线性时间复杂度解决方案的问题，这是一个可怕的解决方案。像这样的递归函数说明了它不如基于循环的解决方案。这需要更多的时间。虽然它可能看起来很优雅，但这是一个可怕的解决方案。
这是一个指数时间复杂度 O(2^n)。我们确定了函数调用的增长，并且由于其指数，我们可以说该算法具有指数时间复杂性。
京公网安备 11010802030320号