千锋教育-做有情怀、有良心、有品质的职业教育机构

手机站
千锋教育

千锋学习站 | 随时随地免费学

千锋教育

扫一扫进入千锋手机站

领取全套视频
千锋教育

关注千锋学习站小程序
随时随地免费学习课程

当前位置:首页  >  技术干货  > 递归算法及其时间复杂度 O(n) 与 O(2^n)

递归算法及其时间复杂度 O(n) 与 O(2^n)

来源:千锋教育
发布人:syq
时间: 2022-09-21 11:35:10 1663731310

  javaScript 算法基础知识第 4 部分:具有线性时间复杂度 O(n) 和指数时间复杂度 O(2^n) 的递归算法。递归是编程中的关键概念之一。作为一种解决问题的方法,它也被广泛用于数据结构和算法中。它帮助我们将大型复杂问题分解为较小的问题。因此,了解递归的时间复杂性对于理解和提高代码效率至关重要。

1

  对于本系列 JavaScript 算法的第 3 部分,您可以参考以下链接。

  第3部分:使用渐近分析推导恒定时间复杂度O(1)

  在本文中,我们将介绍递归算法的两个示例及其时间复杂度。

  具有线性时间复杂度 O(n) 的递归算法

  具有指数时间复杂度 O(2^n) 的递归算法

  首先,简要介绍一下递归。

  什么是递归?

  我们说一个函数是递归函数,如果它直接或间接地调用自己。下面是递归函数的一瞥。

2

  上面的函数是递归函数的一个例子,因为它正在调用自身,但它也是不完整的,因为它会导致无限循环。这是因为该函数没有任何退出条件。但是,这里的关键点是,递归只是从该函数内部调用该函数。

  为了非常清楚地说明这一点,让我们看一个简单的例子。

  示例问题

  创建一个简单的函数来计算输入数字的阶乘。

  如果您不知道什么是阶乘,请使用以下输入查看以下函数的行为。

3

  你拿输入数字,乘以这个数字减去1,然后重复相同的操作,直到你达到1。这就是我们计算阶乘的方式。而且,最后,我们可以编写一个函数来做到这一点。

4

  让我们首先看一下非递归方法。因为递归通常(并非总是)只是常规循环的替代方法。因此,让我们尝试首先使用基于循环的方法解决它。

  功能(基于循环的方法)

5

  因此,这是一个使用正态循环的阶乘函数。使用这样的循环并不是解决阶乘问题的坏方法。但也存在一种不同的方法来使用递归来解决上述问题。而且,正如您将进一步看到的那样,这种递归将允许我们编写更少的代码,这通常是我们可能想要使用递归的原因之一。

  递归解 O(n)

6

  上面的函数是递归的,因为它正在调用自身。在函数中有两件重要的事情要观察,即“if block”和“函数调用”,参数为(n-1)。

  我们将 if 块称为“退出条件”或始终返回值的“基本情况”。并且,将“函数调用”作为“递归步骤”。

  另一件需要注意的重要事情是,我们在递归步骤中将不同的参数传递给函数调用。因为,如果我们再次调用带有n的函数,我们将不会更改任何内容。我们只会得到一个无限循环。

  因此,递归函数应始终具有这两个组件,即“退出条件”和“递归步骤”,否则我们将始终具有无限循环,这将使我们的程序崩溃。

  如果满足基本条件,退出条件或基本情况为我们提供了一种退出函数的方法。

  而且,递归步骤帮助我们通过对同一函数进行递归调用来计算结果,但输入的大小减小。

  这可以表示为函数调用链。就像下面的例子一样,对于一个事实(4),我们将返回4 * fact(3),这给了我们3 * 个事实(2),这将再次给我们2 * 个事实(1)。并且,这最终返回 1,然后将计算的返回值传递给函数调用,从而产生 24。

7

  如何推导递归算法的时间复杂度?

  根据渐近分析,我们仍然可以计算上述函数中的操作。因此,每个操作将执行一次,包括 return 语句中的函数调用。

  但是,由于我们在 return 语句中有一个函数调用。我们启动一个新的函数调用,因此函数中的所有代码都会再次运行多次,直到满足退出条件。因此,我们可以计算递归函数的函数调用次数。因此,我们可以看到,在上面的示例中,我们得到了 4 个函数调用,函数的阶乘为 4。

  在每个函数调用中,我们有一个常量时间,我们的函数中没有任何循环。因此,我们可以将其编写如下。

8

  但是,上述函数调用触发了多个函数调用,即当输入值为n时,n个函数调用。

  因此,我们对多个函数调用的时间复杂度将是,

9

  那就是,

10

  这可以写成,

11

  上面的等式最后只是O(n)。而且,这与我们基于循环的解决方案的时间复杂度相同,即线性时间复杂度。

  虽然这是递归算法的一个非常简单的示例,但我们也有使用递归的算法,因为它们比替代解决方案产生更好的结果。

  递归算法 指数时间复杂度 O(2^n)

  在前面的示例中,递归看起来不错,我们通常可以编写更少的代码来解决问题。但是,让我告诉你,递归并不总是最好的解决方案。为了证明这一点,我们将研究斐波那契数列的递归实现。

  功能

12

  上述函数是一个斐波那契函数,它启动两个递归函数,触发新的函数调用,直到满足退出条件。解析所有这些函数调用后,结果将冒泡并返回到初始函数。此处的这两个函数中的每一个都将返回一个值,然后将这些值相加。

  那么,这种方法有什么问题呢?

  这种方法的错误之处在于,当我们调用它时,该函数会构建一个跨多个分支的嵌套递归函数调用树。

  这可以在下面的示例图中看到,因为n = 4。

13

  如您所见,我们收到了 9 个函数调用,例如 4 个。如果我们使用基于循环的解决方案来完成它,那么我们只会迭代4次。这不是一个好的解决方案,因为即使对于较小的输入数字(如 4),函数调用也有大约 9 次执行。

  类似地,函数调用呈指数级增长,输入数字从 4 线性增加到 6,如下所示。

14

  如果输入数字进一步增加,情况会变得更糟。

  那么这个递归函数的时间复杂度是多少呢?

  这绝对不是O(n),基于循环的解决方案就是这种情况。我们得到了(9)4次处决,(15)次处决5次,(25)执行6次处决。因此,如果我们仅将提供给函数的数量增加 1,则执行次数将呈指数级增长。它不是线性增长的。我们添加的执行次数似乎随着n的增大而增长,并且呈指数级增长。

  因此,这里相对较小的上升需要越来越长的时间。事实上,这个时间尺度的复杂性是指数级的。随着n的每个增量,我们向这个递归树添加全新的分支,而不仅仅是一个函数调用。此外,每个分支都由其他分支组成。结果,这很快增加到我们的机器无法处理的体积。因此,对于我们已经有一个线性时间复杂度解决方案的问题,这是一个可怕的解决方案。像这样的递归函数说明了它不如基于循环的解决方案。这需要更多的时间。虽然它可能看起来很优雅,但这是一个可怕的解决方案。

  这是一个指数时间复杂度 O(2^n)。我们确定了函数调用的增长,并且由于其指数,我们可以说该算法具有指数时间复杂性。

tags:
声明:本站稿件版权均属千锋教育所有,未经许可不得擅自转载。
10年以上业内强师集结,手把手带你蜕变精英
请您保持通讯畅通,专属学习老师24小时内将与您1V1沟通
免费领取
今日已有369人领取成功
刘同学 138****2860 刚刚成功领取
王同学 131****2015 刚刚成功领取
张同学 133****4652 刚刚成功领取
李同学 135****8607 刚刚成功领取
杨同学 132****5667 刚刚成功领取
岳同学 134****6652 刚刚成功领取
梁同学 157****2950 刚刚成功领取
刘同学 189****1015 刚刚成功领取
张同学 155****4678 刚刚成功领取
邹同学 139****2907 刚刚成功领取
董同学 138****2867 刚刚成功领取
周同学 136****3602 刚刚成功领取
相关推荐HOT