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
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.