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

Question

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

Answer 1

这是实现，如果你很好奇：

public int countTokens() {

    int count = 0;

    int currpos = currentPosition;

    while (currpos < maxPosition) {

        currpos = skipDelimiters(currpos);

        if (currpos >= maxPosition)

            break;

        currpos = scanToken(currpos);

        count++;

    }

    return count;

}

我不太熟悉StringTokenizer，但假设maxPosition可以改变（它看起来可以），那么它不是恒定时间。您还必须考虑skipDelimiters和的复杂性scanToken。

Answer 2

不，这不是一定的时间，这是ω(n)哪里n是字符串的长度。

StringTokenizer 的一个简单实现应该采用O(n * d)wheren是字符串的长度，d是分隔符的数量。