Коротко и по делу.
1) Асимптотика исходного кода
- Время: двойной цикл даёт в худшем и среднем случаях $O(n^2)$, где $n=|arr|$.
- Память (без учёта результата): дополнительные структуры не используются, т.е. $O(1)$.
- Память (учитывая результат): в худшем случае может быть до всех пар, т.е. $|res|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ → $O(n^2)$.
2) Слабые места на больших входах
- Время экспоненциально растёт при росте $n$ — неприемлемо для больших массивов.
- Результат может занять квадратичную память (например, все элементы одинаковы и $2x=target$).
- Нельзя работать со стримом/потоком (нужно весь массив в памяти).
- Повторные запросы с разными target полны повторной работы.
3) Улучшения — по сценарию
A. Нужно найти любую одну пару (один ответ), минимизировать время
- Алгоритм: однометочный проход с хеш-таблицей value→index.
- Сложность: время $O(n)$ среднее, память $O(n)$.
- Замечания: для дубликатов хранить только один индекс; вернёт первую найденную пару.
- Пример идеи: при обходе для элемента $x$ проверить, есть ли $target-x$ в dict.
B. Нужно вернуть все пары (все индексы), но массив помещается в память
- Подход 1 (хеш → списки индексов): построить map value→list(indices), затем для каждой уникальной value $v$ брать комплементарный $t-v$ и комбинировать списки.
- Время: $O(n+k)$, где $k$ — число возвращаемых пар (нижняя граница по выводу).
- Память: $O(n+k)$.
- Важное оптимальное обращение с $v=t/2$: число пар = $\left(\genfrac{}{}{0ex}{}{c}{2}\right)$ при $c$ повторениях.
- Подход 2 (сортировка + two-pointer): отсортировать пары (value,index) за $O(n\log n)$, затем двухуказательный проход за $O(n+k)$. Память $O(n)$.
- Лучше при большом числе дубликатов, когда можно комбинаторно считать пары быстрее.
C. Нужна экономия памяти (не хранить все пары) — стриминг
- Использовать генератор (yield) вместо списка: память $O(1)$ кроме буфера; время всё так же зависит от числа пар, но не выделяется память под все сразу.
- Если нельзя хранить весь arr: внешний алгоритм — разбить поток на чанки или использовать внешнюю сортировку (external sort) и затем two-pointer по файлу.
D. Много запросов с разными target на одном и том же arr
- Построить структуру: map value→list(indices) и/или multiset частот. На запрос — для каждого уникального value проверять наличие комплемента: время примерно $O(u+k)$ где $u$ — число уникальных значений.
- Альтернативно, если значения целые и диапазон ограничен, вычислить свёртку (конволюция) частот через FFT за $O(M\log M)$ (где $M$ — размер диапазона) и затем отвечать на запросы за $O(1)$ (возвращает количество пар). Требует целых/небольших диапазонов.
E. Очень большие данные / распределённые / внешняя память
- Разделение по хешу: разбить данные по bucket-ам по value mod p так, что комплементы попадают в известные пары бакетов; затем обрабатывать пары бакетов по очереди (комбинированная внешняя обработка). Позволяет масштабировать MapReduce-подходом.
- Внешняя сортировка + two-pointer по файлам — классический подход с ограниченной RAM.
4) Практические замечания и выбор
- Если нужна одна пара ⇒ хеш-таблица, $O(n)$.
- Если нужно все пары и $k$ потенциально большой ⇒ использовать подход, ориентированный на выходной размер: map→lists или сорт+two-pointer; учитывать $\left(\genfrac{}{}{0ex}{}{c}{2}\right)$ для одинаковых значений.
- Если память критична ⇒ генератор / внешняя сортировка / батчи.
- Если много запросов и значения целые в ограниченном диапазоне ⇒ FFT/свёртка.
- Всегда учитывать, что время обработки будет как минимум пропорционально числу возвращаемых пар $k$.
5) Доп. оптимизация кода
- Использовать генератор (yield) если не нужен весь список.
- Для one-shot задачи возвращать сразу при первом совпадении.
- Для хеш-решения хранить списки индексов при необходимости вернуть все индексы для дубликатов.
- Профилировать: реальный узкий профиль может быть IO или аллокации, а не только алгоритм.
Если нужно, могу привести короткие паттерны-кода для каждого подхода (хеш для одной пары, хеш для всех пар, сорт+two-pointer, генератор).