时间戳

首页 > 解决方案 > 确定以下代码的运行时间（内部循环递归）

algorithm - 确定以下代码的运行时间（内部循环递归）

问题描述

我有以下代码，需要确定这个算法的运行时间。

int res=0; 
if (n <= 1) 
    return 1;
for (int i = 0; i < n; i++) 
    res += Catalan(i) * (Catalan(n - i - 1); 
return res;

由于递归内部的循环，我很难确定运行时间。我知道我需要将其转换为回归公式，然后对其进行分析，但我不知道该怎么做。

标签： algorithmrecursiontimetime-complexitycatalan

解决方案

让我们将您的功能简化为：

    for (int i=0; i< n; i++) 
        res += Catalan(i)*(Catalan(i-1); 
    return res;

这种简化不应影响时间复杂度。

让 n = 1：

   1 
   /\
  0  0

然后我们将有 3 次加泰罗尼亚语函数调用。

如果 n = 2，那么对于 Catalan(i)，我们将有：

     2
     /
    1 
   /\ 
  0 0

对于加泰罗尼亚语（i-1）

   1 
   /\
  0  0

所以总的来说，我们将拥有：

     2      
     /\    
    1  1   
   /\  /\  
  0 0 0  0

如果 i=3，则：

          3
       /     \
      2       2 
     /\       /\
    1  1     1  1
   /\  /\    /\ /\
  0 0 0  0  0 0 0 0

在我看来，这很O(2^n)复杂

推荐阅读