Анализ исходного кода
- Операция `if x not in res` для списка — поиск за линейное время по текущей длине `res`. Для входа длины $n$ суммарная сложность примерно ${\sum }_{i=1}^{n}i=O(n^2)$.
- Память: результирующий список может содержать до $n$ элементов, значит пространство $O(n)$.
Итого: время $O(n^2)$, память $O(n)$.
Более эффективные реализации
1) Для хешируемых элементов (рекомендуемая, среднее время линейное):
```
def unique_order(arr):
seen = set()
res = []
for x in arr:
if x not in seen:
seen.add(x)
res.append(x)
return res
```
- Время: в среднем $O(n)$ (операции множества — амортизированно $O(1)$), худший теоретический случай для плохо распределённых хешей — $O(n^2)$ (редко на практике).
- Память: $O(n)$.
- Сохраняет порядок первых вхождений.
2) Короткая реализация в Python 3.7+ для хешируемых элементов:
```
def unique_order(arr):
return list(dict.fromkeys(arr))
```
- Эквивалентно $O(n)$ в среднем, сохраняет порядок.
3) Если элементы не хешируемы (например, списки):
- Преобразовать элементы в хешируемую форму (если корректно): `tuple(x)` для списков, или использовать ключ-функцию:
```
def unique_order(arr, key=lambda x: x):
seen = set()
res = []
for x in arr:
k = key(x)
if k not in seen:
seen.add(k)
res.append(x)
return res
```
- Если преобразование/ключ невозможны, придётся использовать список `seen` и вернуться к $O(n^2)$.
Компромиссы между скоростью и сохранением порядка
- Самый быстрый способ без сохранения порядка — `set(arr)` за $O(n)$ средне, но порядок теряется.
- Методы с `set`/`dict` дают лучшую скорость и сохраняют порядок первых вхождений при сохранении дополнительной памяти $O(n)$.
- Если память критична и элементы не хешируемы, можно пытаться делать удаление «на месте», но это обычно приводит к $O(n^2)$ времени.
- Выбор зависит от требований: если нужен порядок + скорость → `seen=set()` + список (или `dict.fromkeys`), если порядок не важен → `set(arr)`, если элементы не хешируемы → либо преобразование ключа, либо остаёмся при $O(n^2)$.