O（n）からO（1）へのdeque移動の改善

Question

キューにN個の番号があります。 原点シーケンスは1からNまでです 操作abは、aの前にあるすべての数字を（）移動してから、bの前に挿入します（順序は変更しません）。 「Exit」と表示されたときにキューに入ります。

//I establish q & q1 deque 

while(cin>>commend){ 
    if(commend == "Move"){ 
     cin>>a>>b; 
     int checka,checkb = 0; 

      //search for a,b position 
      //it1,it2 are both iterators 

      for(int m = 0; m < num ; m++){ 
       if(q[m] == a){ 
        it1 = q.begin()+m; 
        checka = 1; 
       } 
       else if(q[m] == b){ 
        it2 = q.begin()+m; 
        con2 = m; //store m in con2 to use below 
        checkb = 1; 
       } 
       else if(checka == 1 && checkb == 1) 
        break; 
      } 

      //con is also a iterator 
      //q1 is a new deque to store the elements before (include)number"a" 
      //procedures below are moving the numbers before(include)"a" and push_front the elements between number "a" and number "b" 

      for(con = it1; con>= q.begin() ; con--) 
       q1.push_front(*con); 
      for(con = it2; con > it1+1; con--){ 
       q1.push_front(*con); 

      } 

      //copy the "swaped" elements from q1 to q 
      //and clear q1 

      for(int m = 0; m<con2-1; m++) 
       q[m] = q1[m]; 
      q1.clear(); 
    } 
} 

しかし、速度はO（N）であると私はこれを改善することができる場所、タスクを完了する必要がある場合、私は知らない：ここでは

は、「移動」に対処するための私のコードですO（1）を使用します。

リンク先を作成することをおすすめしますか？

Answer 1

キュー内の番号のリンクリストと、各番号をキュー内の番号を指すキーとするインデックス（std :: unordered_mapのようなハッシュ）を維持できます。順序を変更するには、O（1）時間内にインデックス内のaとbを検索し、リスト内の数字に移動してリンクポインタを交換して、O（1）時間で順序を変更します。

Answer 2

Moveの機能はO(1)にできません。これは、複雑さが検索操作と作成操作の両方によって決まるためです。検索操作にはO(n)が必要です。データ構造を変更しない限り（これはやりたくない）、縮小することはできません。仮想的にO(1)で検索しても、データが連続したメモリブロックに格納されている場合にのみ、O(1)でコピー操作を実行でき、memcpy()を使用できます。しかし、あなたの検索操作は決してO(n)になることはないので、私によれば、漸近的な境界を変更するための範囲はありません。また、aとbが等しい場合、あなたのプログラムは何もしません。