-
January 11th, 2015, 02:45 PM
#1
a searching algorithm in a circle: 1 unidirectional, 2- Bididirectional
I have 9 numbers: 4 3 2 1 0 -1 -2 -3 -4 they are placed in a circle. Consider them as addresses. that means: every element knows that it has a neighbor that is greater in value on the left, and another neighbor that is smaller in value on the right.
If for example element 0 wants to send a message to element 2, it knows it has to go 2 steps on the left. And if it is searching for -3, it knows it has to go 3 steps on the right.
Each element can perform a search for any other element.
Each element can forward the query to its adjacent neighbor.
IN that case, the worst case scenario would be for element 0 is to search for element 4 or -4, which is 4 steps either way.
Now, if I want to compare the search with this one: The same numbers are arranged in the same circle, however, the search has to go clockwise only, i.e., if I am at 0 and I want to search for 1, I have to walk through all elements clockwise.
Comparing to the first scenario, which one performs better? Should not the first one take half the time of the second one?
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|