Majority Image Algorithm Analysis

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 check if the images in the i and j positions are the same. Show how to solve this problem in O (nlogn) time using a divide and conquer approach

What I thought: Can someone here help me put together 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 the same I. You can use A [i] = A [j] to check if the images in positions i and j are equal. Show how to solve this problem in O (nlogn) time using a division and conquest approach

EDIT MY SOLUTION:

Divide the two-part vector n / 2 - > A and A2 find n1 which is the major element (image) of A find n2 which is the major element (image) of A2 check if the count of n1 or n2 is greater than the mean 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) 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 do not know if I'm correct.

    
asked by anonymous 10.10.2017 / 01:30

1 answer

1

Divide the two-part vector n / 2 - > A and A2 find n1 which is the major element (image) of A find n2 which is the major element (image) of A2 check if the count of n1 or n2 is greater than the mean 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) 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)
    
10.10.2017 / 04:24