QUOTE(fsloke @ 23 Aug, 2008 - 01:25 AM)
Here is the situation or problem raise
You have a basket of marble. Your task is to identity got how many color in the basket.
I prepare a small note book to jot down the identify color of marble.
Algorithm 1:
First I take out one marble from the basket. Oh, it is red color. Then I jot down on my book. Then I find got red color or not in the basket. If got red all take out... Now, the basket no red color marble because I took it all got. In my list got mark red color. After that I take other marble from the basket. Oh blue color. Then I jot down to my book. Then I find all blue color marble then take it out all of then which is blue. Then continue until no marbe in the basket.
In short, in list? No put it in list then go to the basket find all the same color one then throw away.
Algorithm 2
First I take out one marble from the basket. Oh, it is red color. Then I jot down on my book. When I take the second marble. I will compare with my list. If is in my list I will take it out. If not in my list I will jot it down then take it away. This will continue until no marble in the basket.
In short, in list? No put it in list then throw away. Yes then throw away.
May I know have any tool to simulate which algorithm is the best and fastest?
Thank you
I don't know of any tools, but you could of course just calculate the computational complexity. Both algorithms have the same worst case complexity (number of marbles times number of colors), but on average case your second algorithm would be better, as the list of colors is usually shorter than the number of marbles, and you only iterate through the marbles once, and through colors multiple times.
| 