Java StringTokenizer.countTokens() 的时间复杂度是多少

Question

我希望它具有恒定的时间复杂度，但这个名字暗示它实际上是在计算令牌。

Answer 1

这是实现，如果你很好奇：public int countTokens() {&nbsp; &nbsp; int count = 0;&nbsp; &nbsp; int currpos = currentPosition;&nbsp; &nbsp; while (currpos < maxPosition) {&nbsp; &nbsp; &nbsp; &nbsp; currpos = skipDelimiters(currpos);&nbsp; &nbsp; &nbsp; &nbsp; if (currpos >= maxPosition)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; currpos = scanToken(currpos);&nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; }&nbsp; &nbsp; return count;}我不太熟悉StringTokenizer，但假设maxPosition可以改变（它看起来可以），那么它不是恒定时间。您还必须考虑skipDelimiters和的复杂性scanToken。

Answer 2

不，这不是一定的时间，这是ω(n)哪里n是字符串的长度。StringTokenizer 的一个简单实现应该采用O(n * d)wheren是字符串的长度，d是分隔符的数量。