Кратко и по делу.
Анализ исходного кода
- Пусть $n=\text{len(arr)}$. Внутри цикла для каждого $x$ вызывается $\text{arr.count}(x)$ — это проход по всему списку, т.е. $O(n)$ на вызов. Кроме того проверка $x\text{not in result}$ — тоже линейная в размере результата (в худшем случае $\le n$). Итого временная сложность алгоритма в общем виде $O(n^2)$ (квадратичная).
- Потребление памяти: результат может содержать до $O(n)$ элементов, т.е. память $O(n)$.
Проблемы на больших входных данных
- Квадратичное время приводит к очень медленной работе при больших $n$ (TLE/долгие запуски).
- Много лишних проходов по данным (неэффективное использование кеша/CPU).
- Если элементы сложные для сравнения — кошмар по затратам времени.
- При больших объёмах памяти для результата и промежуточных структур (в исходном варианте — только result, но время всё равно доминирует).
Альтернативы (коротко с временными и памятьными оценками)
Обозначения: $n$ — длина входа, $u$ — число уникальных значений.
1) Один проход с использованием множеств (хеширование)
- Идея: поддерживаем set seen и set dups.
- Время: $O(n)$ в среднем (амортизированно для хеш-операций).
- Память: $O(u)$ (для set'ов, в худшем случае $O(n)$).
- Код (сохранение уникальных дубликатов, порядок не гарантируется):
def find_duplicates(arr):
seen = set()
dups = set()
for x in arr:
if x in seen:
dups.add(x)
else:
seen.add(x)
return list(dups)
- Чтобы сохранить порядок первого появления: используйте set для проверки и список для результата + дополнительный set для контроля добавлений; всё ещё $O(n)$ время, $O(u)$ память.
2) collections.Counter (двухфазно)
- Идея: подсчитать частоты, затем выбрать элементы с count>1.
- Время: $O(n)$.
- Память: $O(u)$.
- Код:
from collections import Counter
def find_duplicates(arr):
cnt = Counter(arr)
return [x for x, c in cnt.items() if c > 1]
- Для сохранения порядка: итерировать исходный arr и брать те, у которых cnt[x]>1 и которые ещё не добавлены (контроль через set).
3) Сортировка + проход по отсортированному массиву
- Идея: сортируем, затем сопоставляем соседей.
- Время: $O(n\log n)$.
- Память: $O(1)$ при in-place сортировке CPython (Timsort использует дополнительную память, но асимптотически можно считать $O(1)$ для внешней оценки) или $O(n)$ если создаёте копию.
- Подходит, когда память ограничена, а сравнения дешевые. Порядок оригинала теряется (можно восстановить с индексами).
4) Для данных, не помещающихся в память / распределённые данные
- Варианты: внешний (внешнесортировочный) алгоритм, MapReduce подсчёт, либо потоковые/дисковые хеши (разбить на чанки по хешу и считать внутри чанков).
- При внешней сортировке: временно $O(n\log n)$ дисковых операций; память на диск/буферы.
- Для приближённых ответов можно использовать Count–Min Sketch (приближённые частоты, меньшая память, но возможны ошибки).
Резюме (рекомендации)
- Если элементы хешируемы и нужен быстрый результат: используйте set/Counter — время $O(n)$, память $O(u)$.
- Если нужно экономить память и можно потерять порядок: сортировка $O(n\log n)$ и сканирование.
- Для очень больших данных — внешняя сортировка или распределённые/чанковые методы.
Если нужно, могу привести минимальные реализации вариантов (сохранение порядка/без сохранения).