CODEWITHSUNDEEP
c++algorithmperformancedeque
asdfghj1237890
asdfghj1237890

Reputation: 23

Improvement deque movement from O(n) to O(1)

The task is there are N numbers in a queue. And the origin sequence is from 1 to N. The operation “Move a b” means to move all numbers in front of a (including a) and then insert them in front of b(without changing order) and output the whole queue when "Exit" appear.

Here is my code to deal with the "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();
    }
}

But the speed is O(N) and i don't know where i can improve this if it is required to complete the task with O(1).

Any suggestion except building a linked-list ?

Upvotes: 1

Views: 108

Answers (2)

Sahil Arora
Sahil Arora

Reputation: 885

You cannot do the Move function in O(1). This is because the complexity is determined by both the search and the create operations. Your search operation takes O(n), and you cannot reduce it unless and until you change the data structure(which you won't want to do). Even if you, hypothetically do you search in O(1), you will only be able to do the copy operation in O(1) if the data is stored in a continuous block of memory, and then you can use memcpy(). However, your search operation will never go under O(n), and hence there is, according to me, no scope for changing the asymptotic bounds. Also, your program won't do anything if a and b are equal.

Upvotes: 0

T33C
T33C

Reputation: 4429

You could maintain a linked list of your numbers in the queue plus an index (a hash, like std::unordered_map) with each number as a key pointing to the number in the queue. To change the order, you simply look up a and b in the index in O(1) time, go to the numbers in the List and swap their linking pointers to change their order, again in O(1) time.

Upvotes: 1

Related Questions