238328
27.01.2013 18:13
Имеется список чисел. Нужен алгоритм, который будет проверять, является ли некотрое число N суммой некоторых двух чисел из списка. Ну, и неэффективные решения сразу сосут хуй.
16 comments
recommend
bookmark
subscribeDo you really want to delete ?
Показалось, что ты написал "эффективные решения сосут хуй", потому вот:
filter(partial(eq(item)), map(add, combinations(l, 2)))
а главное память совсем не ест!
но ведь не ест! (если питон третий)
дунно //3.3 никто не использует
ну возьми итеративные аналоги, хуле (imap, ifilter)
а combinations? или оно итератор возвращает? ну норм тогда //в питон2 всё равно ненорм
да, оно в itertools
ну и результат проверять не как len() а как [0] нужно брать и блять ловить кейэррор (если тебя только интересует есть там или нет хоть одна такая сумма)
неэффективно
Почему?
ну ок, неэффективно для большого количества получаемых чисел N
всё равно не понимаю. что конкретно не устраивает? каких оптимизаций ты ожидаешь? тебя не устраивает полный перебор по эффективности, в смысле?
У тупого перебора сложность n^2. Вариант с меньшей сложностью (если я правильно всё понял, n*log(n) сложность считается, правда, конечно же, это всё для худшего случая):
1. отсортировать массив
2. взять два указателя, один на конец, другой на начало.
3. идти первым вверх пока сумма меньше N, идти вторым вниз пока сумма больше N.
Ну, ты понял идею.
да, только после сортировки лущ сделать так: отфильтровать ненужные значения(убрать все числа больше N), а потом для каждого элемента i бинарный поиск на оставшемся отрезке N-i
собственно, фильтрацию тебе мой алгоритм и так сделает, ну, можешь разе что проверку сделать сначала не суммируюя, но глупость это всё.
а по поводу бинарного поиска — ну хуже ведь, а не лучше.
не хуже, а работает