Combien de temps faut-il pour insérer N chaînes différentes de longueur K dans un ensemble?

Вставка N различных строк длины K в множество (set) в Python в среднем работает за время порядка O(N * K), где:

• N — количество строк,
• K — длина каждой строки.

Объяснение:

• Хеширование каждой строки занимает примерно O(K), так как для вычисления хеша нужно обработать все символы строки.
• Вставка в set — амортизированное O(1) по элементу.

Итого: для всех N строк — O(N * K).

Пример:

s = set()
for i in range(N):
    string = generate_string_of_length_K()
    s.add(string)  # хеширование строки + вставка