python - 使用正则表达式进行标记的算法复杂度是多少？

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 文档中读到的内容，“aRegexpTokenizer使用正则表达式将字符串拆分为子字符串”。我假设使用正则表达式对字符串进行匹配将是 O(1)，然后使用 tokenizer.tokenize(s) 将字符串拆分为子字符串将是 O(n)，其中 n 是输入。谢谢你的澄清。

Answer 1

我认为这段代码将是 O(n) 或 n 的大 O。

代码中决定其运行时间的最大因素是正则表达式搜索的字符串的大小。其他行将被视为常量，或 O(1)

假设您的正则表达式要搜索一段文本的时间要长一百倍，那么在决定时间复杂度时，该文本将是压倒性的因素。