how to change the code so that it takes O(1) times
int Queue::getLength() const
// preconditions: none
// postconditions: return the number of elements in the queue
{
int counter = 0; // variable will count items in queue
NodePointer temp;
temp = head; // set pointer to head of list
while (temp != NULL)
{
temp = temp->next; // follow the next pointer
counter++; // add one to our count
}
return counter;
}
int Queue::getLength() const {
return (m_TotalElements);
}
then increment this counter when you insert a element in the queue, and decrement when you remove it.
Just return the value of that counter from this function.
0
shingo43Author Commented:
then increment this counter when you insert a element in the queue, and decrement when you remove it.
Just return the value of that counter from this function.
just to verify that,in the above way,it takes O(1) right?
like if I enquese 5 times and use counter++,it will return 5 and only takes O(1) times? not 5 times?
I am a little confued about counting algorithm orders,so please confirm.
0
Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.
> just to verify that,in the above way,it takes O(1) right?
No the above code is of order O(n), where n is the number of items in the list.
[OK, it is O(1) if there is 1 item in the list.]
0
shingo43Author Commented:
OMG,then how do I change the method to make it O(1) time for counting,thanks
0
shingo43Author Commented:
then increment this counter when you insert a element in the queue, and decrement when you remove it.
Just return the value of that counter from this function.
Is this method right or wrong for the question requirement??thanks
You answered your own question. The only way to make it O(1) is to maintain the count of items in the list as you go. Returning the precalculated count would be O(1). This is useful if you modify the list infreqently, but ask it's count a whole lot. If, however, you add [and remove] item to the list frequently, but rarely ask how many are on the queue, then the O(n) solution is probably more appropriate.
O(n) => the time complexity for the function depends linearly with the number of items in question
O(1) => the time complexity for the function is constant and does not depends on the number of items in questiong
for your implementation, you need to loop through the list as many times as the number of items(n) and thus it is in O(n)
for the counter implementation, you will only need to return the counter which makes it O(1)
it does not matters if you enqueue 5 times as enqueue is another function.
O(5) is equivalent to O(1) and normally, nobody talks in term of O(5) but only O(1)
0
Featured Post
Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.