Solution:
To find the MAX element of the array, we need to rule out (n-1) no.s, which means that we require atleast (n-1) comparisons. If we try to find the 2nd largest element in a similar fashion, we would need another (n-2) comparisons.
If however, we use the tournament model, we can reduce the no. of comparisons for second largest to (n-1)+logn. This involves finding the MAX as above and then finding the second MAX from amongst all those who lost to the MAX. The elements which lost to MAX at each level can be found out by creating a heap like structure of the tournament.
An extension to this is to find the kth largest element in the array.
->This can be found out by conducting k/2 tournaments to find MAX and 2nd MAX as above.
->We can use order statistics algorithm to find the kth largest element in O(n).
->Create heap in O(n). Remove the MAX n times from the heap, in O(k logn) time.
To find the MAX element of the array, we need to rule out (n-1) no.s, which means that we require atleast (n-1) comparisons. If we try to find the 2nd largest element in a similar fashion, we would need another (n-2) comparisons.
If however, we use the tournament model, we can reduce the no. of comparisons for second largest to (n-1)+logn. This involves finding the MAX as above and then finding the second MAX from amongst all those who lost to the MAX. The elements which lost to MAX at each level can be found out by creating a heap like structure of the tournament.
An extension to this is to find the kth largest element in the array.
->This can be found out by conducting k/2 tournaments to find MAX and 2nd MAX as above.
->We can use order statistics algorithm to find the kth largest element in O(n).
->Create heap in O(n). Remove the MAX n times from the heap, in O(k logn) time.
No comments:
Post a Comment