Reputation: 615
I am trying to teach myself order statistics by solving the problem
find the kth largest element in an array in O(n) time.
My Java implementation is as follows below.
Qn: I am unsure of how to determine the complexity of my code. From what I understand, it does not exceed n. Is this correct? Or how should I get this?
Have adapted the algorithm from pg 215, Intro to Algo MIT Press.
package intp;
public class IntP {
public static void main(String[] args) {
int[] qn = {10,22,33,4,5,6,1};
int[] res = {0,0};
int q;
int k =3;
q=k;
while (k>=1){
res = findMax(qn,k);
qn[res[1]]=0;
k=k-1;
}
System.out.println("Largest element number "+q+ " is: "+res[0]);
}
public static int[] findMax(int[] a,int k){
int pos=0;
int max = a[0];
int[] ans= {0,0};
for(int i= 1;i<a.length;i+=2){
if (i+1==a.length){
if (a[i]>max){
max=a[i];
pos=i;
}
break;
}
if (a[i]>a[i+1] && a[i]>max){
max=a[i];
pos=i;
}
else if (a[i+1]>max && a[i+1]>max){
max= a[i+1];
pos=i+1;
}
}
ans[0]=max;
ans[1]= pos;
return ans;
}
}
Upvotes: 0
Views: 269
Reputation:
Repetitive selection of the maximum is a poor way to implement selection of the Kth (except maybe for very small K). It takes worst-case time O(KN).
A better approach is to sort the array, for example using Quicksort, performing in expected O(N.Lg(N)). Anyway, the worst-case time is quadratic, O(N²).
A bit better, Quickselect, a "stripped-off" version of Quicksort. Closer to linear time O(N), but it keeps the worst-case O(N²).
The truly optimal approach (in the asymptotic sense) is that of the Median of Medians, with a guaranteed O(N) behavior.
My preferred implementation of the naïve approach:
for (i= 0; i < n; i++) // Try every element a[i]
{
int r= 0;
for (j= 0; j < n; j++) // Evaluate the rank by counting inferior elements
{
r+= a[j] < a[i] || (a[j] == a[i] && j < i); // Mind the equal elements
}
if (r == k) // Desired rank
return i;
}
Upvotes: 0
Reputation: 5950
First Time complexity of findMax
:
Time(findMax) = 3 + 1/2 n * (4 + 2) + 1 + 3
Time(findMax) = 3 n + 7
Time(findMax) ~ n
Time(findMax) ~ O(n)
Then Time complexity of main
:
Time(main) = 5 + k * (3 + Time(findMax))
Time(main) = k * (3 n + 10) + 5
Time(main) = 3 k n + 10 k + 5
Time(main) ~ k * Time(findMax)
Time(main) ~ O(kn)
Note: I considered any managed instruction as 1 operation
Upvotes: 2