代码之家 › 专栏 › 技术社区 › George Kagan

方法的复杂性

big-o performance

George Kagan · 技术社区 · 16 年前

我有这个方法:

public static int what(String str, char start, char end)
{
    int count=0;
    for(int i=0;i<str.length(); i++) {
        if(str.charAt(i) == start)
        {
            for(int j=i+1;j<str.length(); j++)
            {
                if(str.charAt(j) == end)
                    count++;
            }
        }
    }
    return count;
}

我需要找到的是:

结束每个 (或者是?未在赋值中指定,第3点取决于此) 开始

2) 它的复杂性是什么?答:第一个循环完全遍历字符串,因此至少 O(n) ,第二个循环仅在开始找到char,然后部分找到(索引开始找到了+1)。不过,大O是最坏的情况不是吗?所以在最坏的情况下, 是第一个字符&内部迭代对字符串进行n-1次迭代,-1是一个常量,因此 n 说它的复杂性是O(n^2)是正确的吗

3) 重写它以降低复杂性。
开始最多发生一次 或者更多,如果最多一次,则可以使用一个循环重写方法(具有指示已经遇到了,从那里开始递增每次发生),产生复杂的 O(n) .

不过,以防万一开始 很可能是的 ,因为作业是一门Java课程,我不认为他们会造成这样的歧义。
解决,在这种情况下,是不可能使用一个循环。。。等待
只要有一个变量, 股份有限公司 每次递增开始计数每次是在1号之后遇到的已找到:

inc = 0, count = 0
if (current char == start) inc++
if (inc > 0 && current char == end) count += inc

这也会导致 ? 因为只有一个循环。

是的,我意识到我写了很多呵呵,但我也意识到,通过将我的思想形成文字,我能更好地理解。。。

3 回复 | 直到 13 年前

Matthew Flaschen 16 年前

在任何给定的开始之后,它会为每个结束字符增加“count”。因此,如果有多个开始,它可以为同一个结束多次递增。
如果要在第一个开始后计算结束字符数,只需在for的内部字符后返回count即可。但由于计数的递增次数取决于启动次数,因此最终的psuedo代码是正确的。但是,您需要切换ifs的顺序来处理start==end的特殊情况。您也不需要检查inc>0

inc = 0, count = 0

if (current char == end) count += inc
if (current char == start) inc++

在任何情况下都是O(n)。

Guffa 16 年前

2) 是的,复杂性充其量是O(n),最坏的是O(n^2)。
3) 几乎是对的。您需要在开始字符之前检查结束字符,否则结果并不总是正确的。C#中的示例:

public static int what(string str, char start, char end) {
  int count = 0, mul = 0;
  foreach (char c in str) {
    if (c == end) count += mul;
    if (c == start) mul++;
  }
  return count;
}