Un problema de sumas

Sea v un vector formado por n enteros y sea s un número entero. El problema consiste en determinar de la forma más eficiente posible si existen dos elementos en v, vi y vj (i != j), tales que vi + vj = s.

Es simple hacerlo en tiempo cuadrático O(n2) mediante el algoritmo “de fuerza bruta”:

def sum1_nsq(s, v):
    for i in xrange(len(v)):
        for j in xrange(len(v)):
            if j >= i:
                break
            if v[i] + v[j] == s:
                return True
    return False

pero lo interesante es ver si puede mejorarse este tiempo…

Advertisements

2 thoughts on “Un problema de sumas

  1. […] respuesta a este problema (y al anterior de sumas) en el próximo […]

  2. […] El problema pedía encontrar un algoritmo subcuadrático para determinar si dos elementos en un vector de enteros con una suma dada. Si confiamos en el caracter O(1) de las tablas hash podemos obtener un algoritmo lineal aun más breve que el cuadrático mostrado anteriormente (y sin recurrir al code golfing ): […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s