AO
будет О(N)
Size: a a a
2021 May 14
Q
Ооо thanks 🙏
AO
И там есть какие-то хитрожопые способы через сортировку именно. Которые потом можно и для 3 и для 4-х сум юзать
AO
Но я их так и не понял
Q
Давно на литкоде на сидел , задача из «алгоритмы ,руководство по разработке» Скиена
D
Можно без доппамяти с помощью двух указателей. Создаем указатель на первый и последний элементы, двигаем левый указатель максимально вправо при фиксированном правом пока сумма < x, потом можно сдвинуть правый и двигаться левым, начиная с позиции, на которой он стоит после предыдущего шага.
D
Собственно поэтому массив и отсортирован.
D
Есть также задача 3-SUM, в которой рассматривается сумма трех элементов. Так вот, открытая проблема (причем довльно безнадежная) решить ее за время O(n^k), где k < 2. Причем алгоритм, требующий O(n^2) времени, очень прост (советую подумать на ним).
K
А откуда открытость?
D
В каком смысле?
K
То есть и не найдено решение, и не доказано, что быстрее нельзя?
D
Ага
D
Q
Да ,хорошее решение ,как раз за линию тк в худшем случае указатели сместятся до равенства
Q
Ну всм равенства элементов
Q
Спасибо
EZ
от того что мы очень плохо умеем оценивать сложность алгоритмов)
DK
Граждане, что брать из литературы по плюсам, если из опыта лишь год на олимпиадной проге на тех же плюсах?
BV
если писать прод то брать книгу по архитектуре любую, если для души то саттера и где непонятно смотреть в стандарт и страуструпа