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 ;  
   }
}

再帰関係を使用して時間の複雑さを計算することについての基本的な考えがあります。しかし、私は関係自体を書くことができません。どなたか指示をいただけませんか？

私が理解していることから、問題を毎回 1 つ少ない要素に分割しています (次のノードに移動することによって)。

だから、それは次のようなものでなければなりません

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

このような状況では、Tree メソッドまたは他のメソッドの方が優れているでしょうか?

4

1 に答える 1

0

それはかなり単純です。

時間の複雑さのシーケンスは既にあります

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

また、必要なのは終了条件です。1 つ目は、要素 n を見つけることです。2 つ目は、配列に m < n の m 要素しかないことです。

したがって、count反復ごとに増加するため、時間の複雑さのシーケンスを少し変更する必要があります

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

これは、検索するインデックスとして i を宣言したためです。

これで、最初の終了条件を書くことができます

T(0,i) = Constant

そして、2 番目の終了条件は、i > m の場合とまったく同じT(m,0)で、複雑さのために i を m に切り替えるだけです。

ここで、Constant が 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 に答える