Java StringTokenizer.countTokens() 的时间复杂度是什么？

Question

我希望这个算法的时间复杂度是稳定的，但是它的名字暗示它实际上是在计数标记。

- James Wierzba

---

不，它不是常数时间。 - shmosel

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的复杂性。

- Jacob G.

---

抢先一步了 ;) - JSCoder says Reinstate Monica

Answer 2

OpenJDK的API文档中写到： http://www.docjar.com/html/api/java/util/StringTokenizer.java.html

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; 
 }

所以，是的，它是线性时间。

- JSCoder says Reinstate Monica

---

所以是的 - OP问它是否是常数时间。我猜这里应该是不是。只是一个小注释而已。 - Zabuzard

是的，我把“希望”解释成了“你能确认怀疑吗”。 - JSCoder says Reinstate Monica

Answer 3

不，它不是常数时间，而是ω(n)，其中n是字符串的长度。

StringTokenizer的一个天真实现应该需要O(n * d)，其中n是字符串的长度，d是分隔符的数量。

- Lie Ryan