Алгоритм суммирования подмножества немного быстрее, чем 2 ^ (n/2) в худшее время?

Проанализировав самый быстрый алгоритм суммирования подмножеств, который выполняется за время 2^(n/2), я заметил небольшую оптимизацию, которую можно выполнить. Я не уверен, действительно ли это считается оптимизацией, и если это так, мне интересно, можно ли ее улучшить с помощью рекурсии.

В основном из исходного алгоритма: http://en.wikipedia.org/wiki/Subset_sum_problem (см. часть с заголовком Exponential time algorithm)

• он берет список и разбивает его на два
• затем он генерирует отсортированные наборы мощности обоих за 2 ^ (n/2) времени
• затем он выполняет линейный поиск в обоих списках, чтобы увидеть, является ли сумма 1 значения в обоих списках равной x, используя хитрый трюк.

В моем варианте с оптимизацией

• он берет список и удаляет последний элемент last
• затем он разбивает список на два
• затем он генерирует отсортированные наборы мощности обоих за 2 ^ ((n-1)/2) времени
• затем он выполняет линейный поиск в обоих списках, чтобы увидеть, соответствует ли сумма 1 значения в обоих списках x или x-last (одновременно с одинаковым временем выполнения), используя хитрый трюк.

Если он найдет либо, то я буду знать, что это сработало. Я пытался использовать функции времени Python для тестирования списков размером 22, и моя версия, по-видимому, работает в два раза быстрее.

После запуска приведенного ниже кода он показывает

0.050999879837   <- the original algorithm
0.0250000953674   <- my algorithm

Моя логика для части рекурсии такова: если она работает для списка размером n за 2^((n-1)/1) времени, можем ли мы не повторять это снова и снова?

Есть ли в этом смысл, или я совершенно не прав?

Спасибо

Я создал этот код Python:

from math import log, ceil, floor
import helper  # my own code
from random import randint, uniform
import time

# gets a list of unique random floats
# s = how many random numbers
# l = smallest float can be
# h = biggest float can be
def getRandomList(s, l, h):    
    lst = []
    while len(lst) != s:
        r = uniform(l,h)
        if not r in lst:
            lst.append(r)
    return lst

# This just generates the two powerset sorted lists that the 2^(n/2) algorithm makes.
# This is just a lazy way of doing it, this running time is way worse, but since
# this can be done in 2^(n/2) time, I just pretend its that running time lol
def getSortedPowerSets(lst):
    n = len(lst)
    l1 = lst[:n/2]
    l2 = lst[n/2:]

    xs = range(2**(n/2))
    ys1 = helper.getNums(l1, xs)
    ys2 = helper.getNums(l2, xs)

    return ys1, ys2

# this just checks using the regular 2^(n/2) algorithm to see if two values
# sum to the specified value
def checkListRegular(lst, x):
    lst1, lst2 = getSortedPowerSets(lst)

    left = 0
    right = len(lst2)-1
    while left < len(lst1) and right >= 0:
        sum = lst1[left] + lst2[right]
        if sum < x:
            left += 1
        elif sum > x:
            right -= 1
        else:
            return True
    return False

# this is my improved version of the above version
def checkListSmaller(lst, x):
    last = lst.pop()
    x1, x2 = x, x - last
    return checkhelper(lst, x1, x2)

# this is the same as the function 'checkListRegular', but it checks 2 values
# at the same time
def checkhelper(lst, x1, x2):    
    lst1, lst2 = getSortedPowerSets(lst)    

    left = [0,0]
    right = [len(lst2)-1, len(lst2)-1]

    while 1:
        check = 0
        if left[0] < len(lst1) and right[0] >= 0:
            check += 1
            sum = lst1[left[0]] + lst2[right[0]]
            if sum < x1:
                left[0] += 1
            elif sum > x1:
                right[0] -= 1
            else:
                return True
        if left[1] < len(lst1) and right[1] >= 0:
            check += 1
            sum = lst1[left[1]] + lst2[right[1]]
            if sum < x2:
                left[1] += 1
            elif sum > x2:
                right[1] -= 1
            else:
                return True
        if check == 0:
            return False


n = 22
lst = getRandomList(n, 1, 3000)


startTime = time.time()
print checkListRegular(lst, -50)  # -50 so it does worst case scenario
startTime2 = time.time()
print checkListSmaller(lst, -50)  # -50 so it does worst case scenario
startTime3 = time.time()

print (startTime2 - startTime)
print (startTime3 - startTime2)

Это вспомогательная библиотека, которую я просто использую для создания списка наборов мощности.

def dec_to_bin(x):
    return int(bin(x)[2:])

def getNums(lst, xs):
    sums = []
    n = len(lst)
    for i in xs:
        bin = str(dec_to_bin(i))
        bin = (n-len(bin))*"0" + bin
        chosen_items = getList(bin, lst)
        sums.append(sum(chosen_items))
    sums.sort()
    return sums

def getList(binary, lst):
    s = []
    for i in range(len(binary)):
        if binary[i]=="1":
            s.append(float(lst[i]))
    return s