Какова временная сложность для вложенного цикла в этом случае?

Question

Я пытаюсь токенизировать текстовый файл. Я создал список строк, найденных в текстовом файле, используя readlines (), и планирую перебирать каждое предложение в этом списке, чтобы разбить каждое предложение с помощью re.split (). Затем я планирую просмотреть список, чтобы добавить каждое слово в словарь, чтобы подсчитать, сколько раз встречается каждое слово. Приведет ли эта реализация вложенного списка к O (N ^ 2) или O (N)? Спасибо.

Этот код является лишь примером того, как я планирую реализовать его.

    for sentence in list:
        result = re.split(sentence)
        for word in result:
            dictionary[word] += 1

Answer 1

for sentence in list: # n-times (n = length of list)
    result = re.split(sentence)
    for word in result: # m-times (m = number of words in sentence)
        dictionary[word] += 1

, поэтому время выполнения будет n * m или n-в квадрате.

Лучший способ решить проблему подсчета - использовать collection.Counter.