Image Majority Algorithm Analysis

Asked

Viewed 152 times

0

Algorithm help

A vector with n images A= [1...n] has a majority image I if more than half of the vector images are equal I. You can use A[i] = A[j] to verify that the images at positions i and j are equal . Show how to solve this problem in time O(nlogn) using a division and conquest approach

What did I think: Someone here can help me build an algorithm for this problem. A vector with n images A= [1...n] has a majority image I if more than half of the vector images are equal I. You can use A[i] = A[j] to verify that the images at positions i and j are equal . Show how to solve this problem in time O(nlogn) using a division and conquest approach

EDIT MY SOLUTION:

Divide the vector into two parts n/2 --> A and A2 find n1 which is the majority element( image) of A find N2 which is the majority element (image) of A2 check whether the n1 or N2 count is larger than the middle size plus 1 of vector A.

Algoritmo:
majoritario(V[1......m])
 se (m==1) 
   retorna V[1]
meio= ceil(m/2) pegar o teto
L_elemento= majoritaio(V[1....meio]
R_elemento= majoritario(V[meio+1....m]
  se L_elemento == R_elemento : retornar L_elemento
L_soma = freq(V[1...m],L_elemento)
R_soma= freq(V[1...m], R_elemento)
  se R_soma > meio+1: retorna R_elemento
  se nao se L_soma> meio+1 retorna L_elemento
se não 
  retorna não tem elemento majoritario.
Freq(V[1...m], elemento)
    para i=1 até m 
       se V[1] == elemento
         conta = conta +1
retorna conta.

MY final idea was to pass the halves recursively. The majority algorithm has two recursive calls .

2*T(n/2)

and the element count is resolved at a time O(n) in the worst case. then we have a recurrence 

T(n) = 2T(n/2) +O(n) e pelo teorema mestre
T(n) = aT(n/b) +O(n^c)
c = logb na base a 
c = 1,a=2,b =2 ou seja 
O(nlogn)

I think that would be the resolution, I’m not sure. Thank you.

my idea was to follow this line, but I don’t know if I’m right.

algorithm

  • already managed to solve this problem. I will post the solution

  • Cool, @Matheus Francisco! Would you mind posting the solution in the response field, just below?

  • I posted the solution there in the question just below.. I believe it is that way .

1 answer

1


Divide the vector into two parts n/2 --> A and A2 find n1 which is the majority element( image) of A find N2 which is the majority element (image) of A2 check whether the n1 or N2 count is larger than the middle size plus 1 of vector A.

Algoritmo:
majoritario(V[1......m])
 se (m==1) 
   retorna V[1]
meio= ceil(m/2) pegar o teto
L_elemento= majoritaio(V[1....meio]
R_elemento= majoritario(V[meio+1....m]
  se L_elemento == R_elemento : retornar L_elemento
L_soma = freq(V[1...m],L_elemento)
R_soma= freq(V[1...m], R_elemento)
  se R_soma > meio+1: retorna R_elemento
  se nao se L_soma> meio+1 retorna L_elemento
se não 
  retorna não tem elemento majoritario.
Freq(V[1...m], elemento)
    para i=1 até m 
       se V[1] == elemento
         conta = conta +1
retorna conta.

MY final idea was to pass the halves recursively. The majority algorithm has two recursive calls .

2*T(n/2)

and the element count is resolved at a time O(n) in the worst case. then we have a recurrence 

T(n) = 2T(n/2) +O(n) e pelo teorema mestre
T(n) = aT(n/b) +O(n^c)
c = logb na base a 
c = 1,a=2,b =2 ou seja 
O(nlogn)

Browser other questions tagged algorithm

You are not signed in. Login or sign up in order to post.