1

我正在学习大哦符号。对于下面的代码，我有一个计算字数的程序，跳过分隔符。对于此算法，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);
}
}
4

4 回答 4

6

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

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

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

于 2012-06-18T14:48:23.433 回答
1

没那么简单。假设我们称字符串的长度为 N，长度为delimM。

对于字符串中的每个字符，您调用delim.contains(...)一次或两次（即 O(M)），因此最终复杂度应为 O(N x M)。

于 2012-06-18T14:47:59.157 回答
1

由于这感觉非常像家庭作业（如果是，请添加homework标签），我将提供一些观察而不是解决方案：

您在这里有两个不同的“N”，其中的长度sentence和项目数delim。这些数字可能大不相同。

你需要了解的大哦性能ArrayList<T>.Contains。你知道那是什么吗？

于 2012-06-18T14:49:06.160 回答
0

您必须考虑循环内有多少个循环（以及这些循环走多远）

彼此内部的循环不超过两个，而不是三个。

for (int i = 0; i < sentence.length()-1; i++) { // loop level 1
    boolean isDelim = delim.contains(sentence.charAt(i));  // loop level 2
    if (!isDelim) continue;

    if (!delim.contains(sentence.charAt(i + 1)))  // loop level 2
        count++;
}
于 2012-06-18T14:55:24.350 回答