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

Question

from nltk.tokenize import RegexpTokenizer
s = "Good muffins cost $3.88\nin New York.  Please buy me\ntwo of them.\n\nThanks."
tokenizer = RegexpTokenizer('\w+|\$[\d\.]+|\S+')
tokenizer.tokenize(s)

Будет ли этот код считаться O (n)?

Исходя из того, что я прочитал из документации NLTK, «RegexpTokenizer разбивает строку на подстроки с помощью регулярного выражения».Я предполагаю, что использование регулярного выражения для mach против строки будет O (1), а затем разделение строки на подстроки с помощью tokenizer.tokenize (s) будет O (n), где n - количество символов ввход.Спасибо за любые разъяснения.

Answer 1

Я бы сказал, что этот код будет O (n) или Big-O с n.

Самым большим фактором в вашем коде, определяющим время его выполнения, является размер строки, которую просматривает Regex.,Остальные строки будут считаться константами, или O (1)

Скажите, что если ваше регулярное выражение будет искать фрагмент текста в сто раз дольше, то этот текст будет подавляющим фактором при определении сложности времени.