Улучшение движения деления от O (n) до O (1)

Question

Задача состоит в том, что в очереди есть N номеров. И начальная последовательность от 1 до N. Операция «Переместить ab» означает перемещение всех чисел перед (включая a) , а затем вставить их перед b (без изменения порядка) и вывести весь очередь, когда появляется «Выход».

Вот мой код, чтобы иметь дело с «Move»:

//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) с каждым номером в качестве ключа, указывающего на номер в очереди. Чтобы изменить порядок, вы просто просматриваете a и b в индексе в O (1) раз, переходите к номерам в списке и свопите их указатели привязки, чтобы изменить их порядок, снова в O (1) раз.

Answer 2

Вы не можете использовать функцию Move в O(1). Это связано с тем, что сложность определяется как операциями поиска, так и операций create. Ваша операция поиска принимает O(n), и вы не можете уменьшить ее до тех пор, пока вы не измените структуру данных (которую вы не захотите делать). Даже если вы, предположительно, ищете в O(1), вы сможете выполнить операцию копирования только в O(1), если данные хранятся в непрерывном блоке памяти, а затем вы можете использовать memcpy(). Тем не менее, ваша операция поиска никогда не будет находиться под O(n), и, следовательно, по моему мнению, нет возможности изменять асимптотические границы. Кроме того, ваша программа ничего не сделает, если a и b равны.