Алгоритмическая сложность токенайзера НЛТК

Question

    for line in file:
        token = RegexpTokenizer(r'\w')
        listtoken = token.tokenize(line)

Для этого кода, что будет обозначение Big-O этого кода с точки зрения времени?Будет ли это считаться линейным временем?Я знаю, что token.tokenize создает список токенов для каждой строки в файле.Итак, если вы перебираете каждую строку в файле и вызываете .tokenize, будет ли это очень плохой временной сложностью?

Answer 1

Сложность определенно не линейна, так как вы вызываете функцию (RegexpTokenizer), которая может занять минимальное линейное время, n раз, где n - количество строк в файле.

Так что, если мы предположим,RegexpTokenizer - это O (m), где m - размер строки, сложность всего кода - O (m * n).

Но это предложение не обязательно должно быть правдой, так как для дальнейшего понимания работы таймера,нам нужно взглянуть на внутреннюю работу токенизатора

Таким образом, общее допущение может быть O (n * m), но реальная сложность может быть больше, чем это.

Итак, если вы перебираете каждую строку в файле и вызываете .tokenize, будет ли это очень плохой временной сложностью?

Даже сложность кажется плохой, я думаю, этонеобходимо, если вам нужно разбить каждое предложение на токены.