java - 为使用 arraylist.contains 的算法找到大哦符号

Question

我正在学习大哦符号。对于下面的代码，我有一个计算单词数量的程序，跳过分隔符。对于这个算法，for 循环将针对句子的长度，然后还有迭代到字符串的 contains。所以根据我的说法，这个算法的大哦符号是 O(n^3)。这是正确的还是我遗漏了一些关于大 Oh 符号的信息？

public class wordCount {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    String sentence = "How are you,zak;far: mon. day ?:";
    int count = 1;
    ArrayList<Character> delim = new ArrayList<Character>();
    delim.add(' ');
    delim.add(',');
    delim.add('.');
    delim.add(':');
    delim.add(';');
    delim.add('"');
    delim.add('\'');
    for (int i = 0; i != sentence.length() - 1; i++) {
        if (delim.contains(sentence.charAt(i))) {
            if (!delim.contains(sentence.charAt(i + 1))) {
                count++;
            }
        }
    }
    System.out.println("The count is: " + count);
}
}

Answer 1

不，您不太正确 - 您假设 contains 的 O(n) 中的“n”与您感兴趣的“n”相同. 它不是——它是数组列表的长度。在这种情况下，这是定界符的数量，而不是句子的长度。

所以您的算法实际上是 O(N * M)，其中 N 是句子长度，M 是定界符的数量。如果您将定界符集视为常量且仅将您的句子作为输入，则整个算法的复杂度为 O(N)。

即使您第二次有条件地调用 contains，每次迭代的 contains 调用总数也只有 1 或 2 - 它不能增长到(比如) 分隔符的数量或句子的大小。