|
I need to make a divide&conquer algorithm for finding the dominant element in an array (dominant element = element which exists at least n/2 times in an array within the size n) . All you can do between those elements is compare them (no < relation or > relation) .
And also I need an algorithm which does it in O(n) (doesn't have to be d&c)
Thanks ahead for any help...
|
|
|
|
|
Well, this may not win any awards for style, but have you considered just using a hash table to aggregate the count?
It would be O(n) to hash everything, since I believe hash tables are theoretically in constant time... Then a subsequent O(n) to find the largest value in the hash table.
There's probably a more clever way to do it, but that would get the job done.
|
|
|
|
|
in the name of god
hello
if i know your question true you can do:
1-for i=0 n
B[A[i]]++;
for counting the number of repeating of them.
and then searching for max with O(n);
valhamdolelah.
|
|
|
|
|
That only works if you know the number range... What if the numbers are completely unknown, and can be as high as 2^16... Are you going to have an array that large?
|
|
|
|
|
khomeyni wrote: in the name of god
hello
Are you really in the US as your profile says? And if so, do you talk like this on the job?
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
no i cant yet change it i am from Iran i will change it soon and also yes we talk like this on job but not as this intensity 
|
|
|
|
|
Tim Craig wrote: Are you really in the US as your profile says? And if so, do you talk like this on the job?
I dont find anythin wrong in the way he speaks...
|
|
|
|
|
For the location stated in your profile, you probably wouldn't. Where I am, it would be considered highly unusual.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Hmmm... Strange... 
|
|
|
|
|
I think you need to get out and about and see how the rest of the world lives if you think that is strange.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
I do very well knw wats happening around... but it is offcourse strange wen u look at people and feel uncomfortable wen they spk abt their god or religion.. first stop discriminating people by religion or by any other means jst think and behave thet we al are civilised humans rather than looking at religion and stuff.. v guys are on 21st century  ...
|
|
|
|
|
Well, where this conversation is going, it should probably be move to the Back Room. However, since this thread is so old, I doubt anyone other than you and I are stirring up the dust here.
Do you really think work is the place to discuss religion? I supppose you think it's ok to be asked about your religion when applying for job then? Do you think that developing a regular speech pattern that immediately identifies outsiders to your religious bent is ignoring religion? How can I ignore it if you're talking about it all the time? I quit paying any attention to religion over 50 years ago. But it's hard to ignore those who continually try to ram it down my throat.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
hello, i am searching for solution for two similar combinatorial problems:
1) how many numbers exist such that they consist of exactly N binary digits, have M ones in their binary expansion and at least K of that ones are successive?
1<=N<=1000, 1<=M<=N, 1<=K<=M.
for cases M-K<K i deduced a formula: (N-K+1)*C(M-K,N-K) - (N-K)*C(M-K-1,N-K-1), but i don't know how to calculate it when M-K>=K.
2) there are X red and Y green balls. how many permutations exist such that Z red balls stand in succession?
1<=X,Y<=1000, 1<=Z<=X.
|
|
|
|
|
in the name of god
i want to write an algorithm with order O(nlg(n)) that gets a real input (x) and searches in the array with size N of real numbers to find two elements that the addition of them is x.
i say that we must compare all elements together so how it can be O(nlg(n))?
does it work if we use binary search?how ?i dont know?
valhamdolelah.
modified on Friday, October 30, 2009 3:18 AM
|
|
|
|
|
1. Sort the array in ascending order. (This is O(n lg(n)).
2. Use two integer indexes, i & j, that point to the array elements to add. The first one (i) starts at 0 (the index of the lowest number).
3. Do a binary search in the array to find the array element that is closest to x when added to the element at index 0 (j). If array [i] + array [j] == x, we're done.
4. Loop: Advance i to the next element.
5. While array [i] + array [j] > x, decrease j. If array [i] + array [j] == x, we're done.
6. When array [i] + array [j] < x, go to Step 4. When i >= j, there's no solution and we're done.
|
|
|
|
|
Alan,
With O(n lg(n)) time to sort, doesn't that use up all of the time allotted (overall time was to be O(n lg(n)))? Wouldn't a B+ tree sort speed up that somewhat to leave a little time for the combinatorial arithmetic? With a B+ tree (n-ary tree) you eliminate many wrong values instead of just two at each step as is done in a binary tree. Once the array of values was sorted, the B+ tree search would also find the correct value quicker than O(n lg(n)) as would be the case using a binary search for the second value.
Dave.
|
|
|
|
|
Big O notation is a measure of the execution time/complexity relative to the input size.
Hence, O(n log(n)) means that the complexity in whatever unit is equal to C * n * log(n) where C is a constant. If you add an extra statement to your inner loop, you're increasing C without increasing the Big O complexity.
We say it this way, because all we're trying to measure is how much longer it would take if, say, we doubled the input size. For an O(n) algorithm, doubling the input will double the complexity.
So in essence...
O(n log(n)) + O(n log(n)) = O(n log(n))
|
|
|
|
|
O(IC)
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
|
|
|
|
|
|
I understand Big O, but in this case, after the sort, for each item, you do a binary search on the array looking for a value that when added to the initial value equals some X. Anything you do to speed up this process will help more than just removing some instruction from the inner loop. You have just added another (n (n log(n))) timeslice to the inner loop, not just some constant.
Dave.
|
|
|
|
|
But you're not doing a binary search on each item. You're doing one sort and one binary search.
Think of it this way... Say the sort and the next operation were each O(n)... Obviously they wouldn't be, but as an example. Then you're doing an O(n) followed by an O(n), or 2 * O(n). But in Big O, we eliminate constants, so it simplifies to just O(n)...
If the two operations are of different complexity, we take the larger one... If it was O(n log(n)) followed by O(n), we'd say the Big O was O(n log n).
|
|
|
|
|
Ian Shlasko wrote: You're doing one sort and one binary search.
But you are not doing that, you are doing the binary search n times looking for a pair that add up to the constant X.
Dave.
|
|
|
|
|
Sorry, mixed it up a bit, but I'm still right about the complexity.
A binary search is O(log n)... And we'd be doing that n times... Hence, O(n log(n)) for all of the searches.
But this is still done AFTER the sort, not inside it, so it adds to the sort instead of multiplying with it.
|
|
|
|
|
You had it right the first time -- Only one binary search is done. It's done to find the upper bound of number pairs that could possibly add up to x.
|
|
|
|
|
I agree with your algo, however I would rephrase it in a more symmetric way, making the O(n) part more clear:
1. Sort the array in ascending order
2. let int i=0 and int j=n-1
3. if i>=j then search is over
4. calculate sum=array[i]+array[j]
5. if sum<x, increment i and goto (3)
6. if sum>x, decrement j and goto (3)
7. since sum==x, solution found (either stop; or increment i, decrement j and goto 3)
(1) is O(n ln(n))
(2)-(7) is O(n) as i and j move towards each other in steps of 1
hence overall O(n ln(n))
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
