Сны

[soloviewoff]

Приснилось, что кто-то допытывался от меня алгоритм нахождения суммы чисел на интервале в отсортированном массиве.  Лучше, чем O(длина интервала).  Без предобработки.  Хорошо, что я проснулся.

Comments

[olenusha]

А сможете за О() найти подмассив идущих подряд чисел с наибольшей суммой?
Числа могут быть отрицательными и естественно они не отсортированы.
Недавно кто-то рассказал задачу. Показалось забавно...

[soloviewoff]

Эту задачу я знаю. Прочитал впервые в Жемчужины Программирования, если не ошибаюсь, про нее. И, честно говоря, не помню, допер я до алгоритма Кадана сам в тот раз или подглядел в ответ.

cur_sum = 0
max_sum = 0
for x in xs:
cur_sum = max(0, cur_sum + x)
max_sum = max(max_sum, cur_sum)
print max_sum

[olenusha]

Ага, нехитро и красиво...

[morfizm]

Красиво

[morfizm]

Подозреваю, что если устраивает приблизительный ответ и существует квантовый компьютер, то может выйти и саблинейно.

[soloviewoff]

Про квантовые компьютеры надо почитать - я в них дуб.

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

[morfizm]

Кстати да, без всяких квантовых компьютеров, обычным параллельным processing'ом можно посчитать за O(logN).
Время - это самая главная характеристика. Операции не всегда даже можно правильно оценить.

[soloviewoff]

Логарифм только при большом / бесконечном количестве ресурсов (процессоров) будет, так что все как обычно упирается в деньги :)