0

Dado um vetor V de inteiros, ordenado, e um valor s, escrever um algoritmo de complexidade O(n) para calcular quantos pares de números têm soma s. Neste vetor poderá haver números repetidos. Note que, se V contêm p ocorrências do número x e q ocorrências de y e se x+y = s, o total de pares relativos a x e y com soma s é p*q.

Consegui fazer para quando não tem números repetidos, mas não consigo adaptar...

v=[2,5,8,20,24,30] #vetor de exemplo. S=50. Nesse caso a única dupla é (20,30)

c=0
i=1
j=1
while i < j:
   se V[i] + V[j] < s:
         i=i+1
   senão se V[I] + v[J] > S;
         j = j+1
   senão:
         c = c+1
         i=i+1
         j=j+1
escrever(d) 
5
  • Que linguagem é essa? Commented 1/09/2019 às 22:54
  • Não importa a linguagem, pode ser pseudocódigo @MauryDeveloper
    – Bakun
    Commented 1/09/2019 às 23:02
  • não é nenhuma específica
    – Bakun
    Commented 1/09/2019 às 23:02
  • Tem várias gralhas de escrita no seu pseudo-código. Não era suposto o j começar na posição final do array e ir descendo ? Se o fizer dessa forma não vejo problemas face a números repetidos.
    – Isac
    Commented 2/09/2019 às 10:48
  • O mesmo numero pode ser utilizado para formar um par? Commented 2/09/2019 às 11:57

2 Respostas 2

1

Fiz um exemplo de código em python, primeira coisa que pensei foi em fazer utilizando 2 for porem sabemos que o nível de complexidade disso seria de O(n^2). Então partindo deste principio poderíamos utilizar busca binaria, ou seja, iriamos percorrer cada item do array e para cada item faríamos uma busca binaria para verificar se possui algum par para esse item. Porem mesmo utilizando busca binaria para isso ele não ficaria com a complexidade de O(n), e para isso existe este outro algoritmo no qual não me lembro o nome onde você percorre o array uma só vez, e para cada item percorrido você armazenaria seu complemento.

Busca linear

A busca linear ira realizar 2 for e ir somando cada item, caso o item seja igual a soma ele ira adicionar a lista. Exemplo em python:

def busca_linear(vetor, valor):
  '''Busca linear, essa busca ira percorrer cada
  elemento do array e verificar se os pares podem
  se juntar, porem isso faz com que tenhamos que
  percorrer o array 2 vezes fazendo com que o nível
  de complexidade seja de О(n^2).
  '''
  pares = list()

  for i in vetor:
    for j in vetor:
      if i + j == valor:
        pares.append((i, j))

  print('[BUSCA_LINEAR] Pares achados: {}'.format(pares))

Busca binaria

Em resumo o que a busca binaria faz e utilizar a ideia de dividir e conquistar, ou seja, ela ira pegar o meio do vetor e verificar se o numero a ser encontrador e o numero do meio, caso contrario verifica se o numero seria maior ou menor que o numero do meio, se for menor ele continua a busca para o lado menor se for maior ele busca para o lado maior. Caso queira estudar mais sobre busca binaria veja a wiki em en ou pt. Exemplo em python:


def busca_binaria(vetor, low, high, valor):
  '''Busca pelo elemento valor e retorna seu index

    param vetor: Lista
    param low: Menor index
    param high: Maior index
    param valor: O valor a ser buscado

    Retorna o index do valor caso tenha sido encontrado,
    caso contrario ele retorna -1
  '''

  while low <= high:

    mid = low + (high - low) / 2

    if vetor[mid] == valor:
      return mid
    elif vetor[mid] < valor:
      low = mid + 1
    else:
      high = mid - 1

  return -1


def achar_pares_binaria(vetor, valor):
  '''Ira percorrer uma vez o vetor, porem para cada item do vetor
  ele ira realizar uma busca binaria para achar seu par, buscas
  binarias podem ser O(n) no melhor caso e O(log n) no pior caso.
  '''

  pares = list()

  for i in vetor:
    # Busca o index do valor que completaria o par do mesmo
    par = busca_binaria(vetor, 0, len(vetor) - 1, valor - i)

    if par > 0:
      pares.append((i, vetor[par]))

  print('[ACHAR_PARES_BINARIA] Pares achados: {}'.format(pares))

Solucao O(n)

Percorre cada item do vetor e armazena qual seria seu par para completar a soma. Para cada item do vetor ele ira armazenar seu complemento por exemplo se a soma for 10 e o vetor [1, 2, 9, 24, 30], o primeiro item do vetor seria 1 seu complemento seria 9 então ele armazena o valor 9. Quando ele chegar no valor de nove no array ele ira verificar se esse valor esta na lista de complementos, caso sim o mesmo ira adicionar a lista de pares. Exemplo em python:

def achar_pares(vetor, valor):
  '''Percorre cada item do vetor e armazena qual seria seu par
    para completar a soma.
  '''

  pares = list()
  complementos = list()

  for i in vetor:
    if i in complementos:
      pares.append((i, valor - i))

    complementos.append(valor - i)

  print('[ACHAR_PARES] Pares achados: {}'.format(pares))

Todas as funções e seus tempos

Neste código abaixo coloquei todas as funções descritas a cima, o código foi feito em python e o mesmo ira calcular o tempo de execução de cada função e no final ira imprimir em ordem de execução.

# -*- coding: utf-8 -*-
import time

def busca_linear(vetor, valor):
  '''Busca linear, essa busca ira percorrer cada
  elemento do array e verificar se os pares podem
  se juntar, porem isso faz com que tenhamos que
  percorrer o array 2 vezes fazendo com que o nivel
  de complexidade seja de О(n^2).
  '''
  pares = list()

  for i in vetor:
    for j in vetor:
      if i + j == valor:
        pares.append((i, j))

  print('[BUSCA_LINEAR] Pares achados: {}'.format(pares))


def busca_binaria(vetor, low, high, valor):
  '''Busca pelo elemento valor e retorna seu index

    param vetor: Lista
    param low: Menor index
    param high: Maior index
    param valor: O valor a ser buscado

    Retorna o index do valor caso tenha sido encontrado,
    caso contrario ele retorna -1
  '''

  while low <= high:

    mid = low + (high - low) / 2

    if vetor[mid] == valor:
      return mid
    elif vetor[mid] < valor:
      low = mid + 1
    else:
      high = mid - 1

  return -1


def achar_pares_binaria(vetor, valor):
  '''Ira percorrer uma vez o vetor, porem para cada item do vetor
  ele ira realizar uma busca binaria para achar seu par, buscas
  binarias podem ser O(n) no melhor caso e O(log n) no pior caso.
  '''

  pares = list()

  for i in vetor:
    # Busca o index do valor que completaria o par do mesmo
    par = busca_binaria(vetor, 0, len(vetor) - 1, valor - i)

    if par > 0:
      pares.append((i, vetor[par]))

  print('[ACHAR_PARES_BINARIA] Pares achados: {}'.format(pares))


def achar_pares(vetor, valor):
  '''Percorre cada item do vetor e armazena qual seria seu par
    para completar a soma.
  '''

  pares = list()
  complementos = list()

  for i in vetor:
    if i in complementos:
      pares.append((i, valor - i))

    complementos.append(valor - i)

  print('[ACHAR_PARES] Pares achados: {}'.format(pares))


def main():
  vetor = [1, 2, 5, 8, 9, 9, 20, 24, 30]
  valor = input('Valor a ser buscado dentro do array ({}): '.format(vetor))

  times = list()
  start = time.time()
  busca_linear(vetor, valor)
  times.append(time.time() - start)

  start = time.time()
  achar_pares_binaria(vetor, valor)
  times.append(time.time() - start)

  start = time.time()
  achar_pares(vetor, valor)
  times.append(time.time() - start)

  for t in range(len(times)):
    print("Tempo [{}] de: {}".format(t, times[t]))

if __name__ == '__main__':
  main()

Saída:

Valor a ser buscado dentro do array ([1, 2, 5, 8, 9, 9, 20, 24, 30]): 10
[BUSCA_LINEAR] Pares achados: [(1, 9), (1, 9), (2, 8), (5, 5), (8, 2), (9, 1), (9, 1)]
[ACHAR_PARES_BINARIA] Pares achados: [(1, 9), (2, 8), (5, 5), (8, 2)]
[ACHAR_PARES] Pares achados: [(8, 2), (9, 1), (9, 1)]
Tempo [0] de: 0.000350952148438
Tempo [1] de: 0.000414133071899
Tempo [2] de: 0.000170946121216
0

Olá, fiz o código em linguagem c, o vetor V é estático, mas o valor de S é um valor de entrada. O programa pega os pares que a soma é igual a S. O código está comentado em linhas chaves. Qualquer duvida só perguntar.

int v[] = {2,5,8,20,24,30};
int s, controle=0; 
int par1[TAM], par2[TAM]; // Vetores onde vão ser guardados os valores que se somados são igual a S
printf("Valor de S: ");
scanf("%d",&s);
for(int i = 0; i < sizeof(v)/sizeof(int); i++){ // Laço de repetição que vai de 0 ao tamanho do vetor V
    for(int j = 0; j < sizeof(v)/sizeof(int); j++){
        if(v[i] + v[j] == s){ // Se o valor da soma for igual a S a atribuição é feita logo a baixo
            par1[controle] = v[i];
            par2[controle] = v[j];
            controle++;
        }
    }
}
for(int i = 0; i < controle; i++){ 
    printf("Pares: %d %d \n", par1[i], par2[i]); // Printa os pares na tela 
}
}
1
  • 1
    Esta solução não responde à complexidade pedida no enunciado de O(n)
    – Isac
    Commented 2/09/2019 às 10:47

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .