递归函数的时间复杂度

如何找到递归函数的时间复杂度?

让我们首先了解求时间复杂度的基本概念。我们假设程序中的每条语句都需要一个单位的时间来执行。

让我给出那个背后的想法。假设有一些书存放在一个地方，您必须移动这本书并将其放在架子或架子上。需要多少时间?也许半秒，四分之一秒，也许如果有人工作得很慢，可能需要一秒钟才能把一本书放在那里。时间因人而异。所以，我们不说秒或毫秒，我们说一个时间单位。如果以货币为例，一美元，一卢比，一英镑。我们说一个，但市场价值可能会有所不同。所以，我们说一美元或一单位货币。

同样，我们假设每条语句都需要一个单位时间。如果该语句重复多次，那么我们需要计算它执行多少次的频率。这足以分析我们的功能。

查找递归函数的时间复杂度的示例：

我们将使用以下函数。也就是说，我们将计算以下递归函数的时间复杂度。

现在，让我们看看上面的函数(fun1)在做什么。它什么都不做，只是打印。它只是打印 n 的值。

打印需要多少时间?

打印需要一个单位的时间。

printf 在那里写了多少次?

那里只写了一次 printf。但这是一个递归函数。所以，它一次又一次地呼唤自己。

由于它是一个递归函数，让我们找出 printf 函数执行了多少次。正如我们在递归工作原理一文中已经讨论过的，我们可以使用跟踪树或递归树来找出这一点。

正如您在上面的跟踪树中看到的，它首先打印值 3，然后打印 2，然后打印值 1。这意味着 printf 语句执行了 3 次。因此，当 n 值为 3 时，此递归函数将需要 3 个单位的时间来执行。如果我们将 n 值设为 5，那么执行此递归函数将需要 5 个单位的时间。

所以，我们可以说对于 n 它将花费 n 个单位的时间。回到这个例子，如果我们必须在书架上放一本书。你需要一个单位的时间，10本书你需要10个单位的时间。因此，对于 n 本书，您将获得 n 个时间单位。您需要记住的最重要的一点是时间取决于书籍的数量。

时间可以表示为 n 的顺序，即O(n)。花费的时间是n的顺序。

使用递归关系的时间复杂度：

还有另一种方法可以找到时间复杂度，即使用递归关系。让我们看看如何编写递归关系以及如何解决它以找到递归函数的时间复杂度。现在，让我们使用递归关系计算以下递归函数的时间复杂度。

我们假设上述函数花费的时间是 T(n)，其中 T 代表时间。如果 fun1() 花费的时间是 T(n)，那么总时间应该是该函数内的语句所花费的所有时间的总和。

那么，让我们看一下声明。每条语句都需要一个单位的时间来执行。请参阅函数内部有一个条件语句(if (n > 0))。执行需要多少时间，只需执行一个单位时间。然后是一个printf语句，这也需要一个单位时间。

然后那里多了一个函数调用语句(fun1(n-1))，需要多少时间，也需要一个单位时间。不，这是不正确的。它不会花费一个单位的时间。这是一个函数调用。它应该是该功能所花费的总时间。这不仅仅是一个正常的说法。它会再次调用自己。所以，在那之后还有更多的东西。那么，我们需要知道该函数调用需要多少时间?

让我们仔细看看。我们所说的 fun1(int n) 函数调用，总时间是 T(n)。那么这个fun1(n-1)和fun1(int n)类似，这里是n-1。所以，这个函数所花费的总时间将是 T(n-1) 时间。那么什么是T(n)?正如我们所说的声明所花费的所有时间的总和。因此，让我们取T(n) =T(n-1)+2的总和。为了更好地理解，请看下图。

因此，当n>0时，递归关系为T(n)=T(n-1 )+ 2。当n=0时会发生什么，它只会检查条件，它不会进入其中并会出来。只是检查条件，所以需要一个单位的时间。为了更好地理解，请看下图。

所以，这是由 fun1 函数形成的递归。因此，递归函数的时间复杂度可以用递归关系的形式表示。