找到我使用arraylist.contains的算法的大哦符号

Question

我正在学习大哦记谱法.对于下面的代码,我有一个计算单词数量的程序,跳过分隔符.对于这个算法,for循环将是句子的长度,然后包含迭代到字符串的包含.所以根据我的说法,这个算法的大哦符号是O(n ^ 3).这是正确的还是我错过了一些关于大哦符号的东西？

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

不,你不是很正确 - 你假设O(n)contains的"n"与你感兴趣的"n"相同.它不是 - 它是数组列表的长度.在这种情况下,这是分隔符的数量,而不是句子长度.

所以你的算法实际上是O(N*M),其中N是句子长度,M是分隔符的数量.如果您将分隔符集视为常量而仅将您的句子作为输入,则整个算法为O(N).

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