int a[sizeA],b[sizeB],c[sizeC];
for(int ai=0;ai<sizeA;ai++)
{
for(int bi=0;bi<sizeB;bi++)
{
for (int ci=0;ci<sizeC;ci++)
{
if((c[ci]==b[bi]) && (b[bi]==a[ai]))
{
cout<<"Match found";
break;
}
}
}
}
Optimizing this algorithm
Author
I have three large arrays. Data in all of them is ordered in ascending order. I'd like to be able to quickly find occurance of a same number in all three arrays. Let's say I start with a basic straightforward algorithm.
This algorithm has complexity of Big O(n^3). Which is just about the worst solution. I can decrease complexity by making this algorithm intelligent by taking advantage of its sort order by moving index pointer of BI and CI depending on the value and sort order. Problem is that my co-worker tells me that I can solve this task with Big O(n) complexity. But I just don't see it. Binary search is out of the question as it has lousy efficiency comparing to O(n). Any ideas to improve efficieny to O(n)?
I don't quite understand your question, but binary search is O(logn) which is so much better than O(n).
Any searching algorithm will not be O(n). Are there any keys to each item that are used for hashing? Hashing is o(n).
Here's a simpler problem. Solving this problem will make it easy for you to solve your problem.
You have two stacks of cards. Each stack contains lots and lots of cards, each with a number from 1 to a billion. Each stack is sorted from lowest to highest. Your task is to determine if the two stacks have any cards in common.
But there's a complication. You can only see the card on top of each stack at any one time (no rifling through the stack). And once you take a card off the top of a stack, you have to throw it away and never think about it again. In other words, you only get one pass through the stacks.
How do you do this?
You have two stacks of cards. Each stack contains lots and lots of cards, each with a number from 1 to a billion. Each stack is sorted from lowest to highest. Your task is to determine if the two stacks have any cards in common.
But there's a complication. You can only see the card on top of each stack at any one time (no rifling through the stack). And once you take a card off the top of a stack, you have to throw it away and never think about it again. In other words, you only get one pass through the stacks.
How do you do this?
Author
I'll look into hashing. Looks like i'll have to scrap that idea. It's a non-essential part anyways. Spent to much time on this today already. Got a headache...
Quote:Original post by Sneftel
How do you do this?
oooo - pick me pick me *jumps up and down with hand in the air*
Well, Sneftel has the answer for you, but why didn't you just ask your coworker how to do it? If they know how, then it would be a lot faster than posting here and waiting for response.
karg
karg
- Compare the first 3 values for a match.
- Within a loop begin at the beginning of each array.
- Chose the largest result as a baseline and increment the index of the other arrays independantly until their value is greater or equal to the chosen baseline value. Compare for a match after each increment in index.
- repeat until the arrays are exhausted.
OR:
- Within a loop begin at the beginning of each array.
- Compare current three values for match
- Increment the index of the array with the smallest value, but don't overflow it. Establish a Tie-breaking rule for multiple same values.
- Repeat until all arrays are exhausted.
The second method is a cleaner implementation.
[EDIT] - Added the bit about comparing after each increment and put the first comparison before the loop.
[EDIT] - Added second algo.
- Within a loop begin at the beginning of each array.
- Chose the largest result as a baseline and increment the index of the other arrays independantly until their value is greater or equal to the chosen baseline value. Compare for a match after each increment in index.
- repeat until the arrays are exhausted.
OR:
- Within a loop begin at the beginning of each array.
- Compare current three values for match
- Increment the index of the array with the smallest value, but don't overflow it. Establish a Tie-breaking rule for multiple same values.
- Repeat until all arrays are exhausted.
The second method is a cleaner implementation.
[EDIT] - Added the bit about comparing after each increment and put the first comparison before the loop.
[EDIT] - Added second algo.
Author
My coworker is sort of an asshat, i bet this algorithm is probably not even optimizable to O(n). All three arrays have different sets of sorted numbers. There might not even be a number that occurs in all arrays. That's why I need to do this.
Quote:Original post by Karg
Well, Sneftel has the answer for you, but why didn't you just ask your coworker how to do it? If they know how, then it would be a lot faster than posting here and waiting for response.
where's the fun in that?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
