0

我想在链表的末尾找到第 i 个位置的数据。我使用递归编写了这段代码：

节点结构：

struct Node
{
   int data;
   struct Node * next;
}

代码 ：

int i = 10;

int find ( Node * ptr, unsigned int count )
{
   if( nullptr == ptr )
   {
      ++ count;
      return count;
   }

   count = find ( ptr->next , count );
   if( i == count )
   {
      std::cout << "Successful here: " << ptr->data << std::endl; 
      exit ( -1 ) ;
   }

   else
   {
      ++ count;
      return count ;  
   }
}

我对使用递归关系计算时间复杂度有基本的想法。但我无法编写关系本身。有人能给个方向吗？

据我了解，我每次都将问题分成一个更少的元素（通过移动到下一个节点）。

所以它应该是这样的

T(n) = T(n-1) + 常数

在这种情况下，树方法或任何其他方法会更好吗？

4

1 回答 1

0

这相当简单。

您已经有了时间复杂度的序列

T(n) = T(n-1) + Constant

你还需要你的结束条件。首先是你找到元素n。第二个是您的数组只有 m 个元素，其中 m < n。

因此，由于您count的每次迭代都在增加，我们必须将时间复杂度序列稍微更改为

T(i,c) = T(i-c, c+1) + Constant

这是因为您将 i 声明为要查找的索引。

所以现在对于第一个结束条件我们可以写

T(0,i) = Constant

T(m,0)对于第二个结束条件，如果 i > m 我们只是将 i 切换为 m 以提高复杂性，则完全相同。

现在让我们假设常量等于 1。

然后我们得到以下等式

T(i,0) = T(i-0,1) +1 = T(i-1,2) +2 = T(i-2,3) +3 = T(i-3,4) +4 = .... = i+1

所以复杂性是T((min(i,m),0) = i+1或T(i,0)在O(i).

您可以将代码更改为

int find ( Node * ptr, unsigned int i ){
       if( nullptr == ptr )
          return i;

       if( i == 0 )
       {
          std::cout << "Successful here: " << ptr->data << std::endl; 
          return 0;
       }
       return find ( ptr->next , --count );
    }

所以你会有序列T(n) = T(n-1) + Constant

于 2013-06-25T12:00:20.997 回答