Сны

[soloviewoff]

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

Comments

[morfizm]

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

[soloviewoff]

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

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

[morfizm]

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

[soloviewoff]

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

[morfizm]

Я думаю, по процессору на каждые несколько байт памяти - это не очень отдалённая перспектива. Если ты не время оптимизируешь, а стоимость, причём именно на сегодняшний день, то это другое дело, конечно :)