Вы спрашиваете конкретно о временной сложности, но найти временную сложность легче, когда код чистый. Итак, я: 1. почищу код; 2. Найдите временную сложность и обсудите возможные улучшения.
Очистите код
Во-первых, вместо создания list_a, list_b, ..., создайте dict list_by_first_letter. Нам не нужно беспокоиться об индексах:
for k in keys:
letter = k[0][0]
if not('a' <= letter <= 'z'):
letter = 'UNK'
list_by_first_letter.setdefault(letter, []).append(k)
setdefault проверит, является ли letter уже ключом в dict, а иначе создаст его и сопоставит со значением по умолчанию ( пустой список [] здесь).
А затем, чтобы найти дубликаты:
for alphabet_list in list_by_first_letter.values():
check_based_alphabet(alphabet_list)
Теперь нам нужно очистить check_based_alphabet. Заменяю while на for. Поскольку вы сопоставляете каждый элемент со всеми остальными, которые у вас есть:
def check_based_alphabet(alphabet_list):
for k in range(len(alphabet_list)):
first_key = alphabet_list[k]
for j in range(len(alphabet_list))):
second_key = alphabet_list[j]
if first_key[1] != second_key[1]:
distance = td.jaccard(first_key[0], second_key[0])
if distance > 0.7:
duplicate_list.append([first_key[0], second_key[0]])
У вас может быть проблема: вы сравниваете alphabet_list[0] с alphabet_list[1], alphabet_list[2], ..., затем alphabet_list[1] с alphabet_list[0], alphabet_list[2], .... Если ваш td.jaccard симметричный c, вы получите каждую пару дважды. Чтобы избежать этого, используйте:
...
for j in range(k+1, len(alphabet_list))):
...
Вы избавитесь от дубликатов, поскольку second_key всегда после first_key в списке. (Я не буду утверждать, что код теперь полностью чистый, но он, по крайней мере, читается.)
Временная сложность
Теперь мы можем найти временную сложность. Во-первых, временная сложность check_based_alphabet равна O(n^2 * complexity of td.jaccard), где n - это номер элемента в подсписке. Это очевидно из-за двух составных циклов.
Если N - количество элементов в списке, у вас есть глобальная временная сложность O(n1^2 * complexity of td.jaccard) + O(n2^2 * complexity of td.jaccard) + ..., где N = n1 + n2 + ..., то есть O(N^2 * complexity of td.jaccard):
- В худшем случае у нас есть
N = n1 и n2 = ... = 0, и результат тривиален. - В лучшем случае у нас
n1 = n2 = ... и 27 * O((N/27)^2 * complexity of td.jaccard) и это все еще O(N^2 * complexity of td.jaccard), хотя это может быть быстрее.
Кажется, трудно улучшить эту временную сложность. Посмотрите на свою пробную версию: вы группируете ключи в сегменты (все ключи, которые начинаются с одной и той же буквы) и сравниваете каждый ключ со всеми ключами того же сегмента. Хорошая идея, но недостаток в том, что размер ведер все равно зависит от N. Чтобы уменьшить временную сложность, вы должны создавать корзины фиксированного размера. Это невозможно, если td.jaccard и / или ключи не имеют определенных свойств c.
(Пример определенных свойств c: представьте, что у вас есть список различных целых чисел, и эти два целые числа i, j называются «дубликатами», если |i -j| < K, где K не зависит от N. Вы можете сравнивать все пары целых чисел (O(N^2)), но вы также можете сортировать целые числа (O(N lg N) в общем случае c), а затем сравните каждый элемент отсортированного списка со следующими целыми числами K (выше, все целые числа не менее i + K, следовательно, не дублируются): O(N * K). Следовательно, время сложность O(N (K + lg N)) лучше, чем O(N^2).)