performance - 方法的大 O 复杂度

Question

我有这个方法:

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

我需要找到的是:

1)它在做什么？答案:计算 之后结束出现的总数每个 (或者是吗？没有在作业中指定，第 3 点取决于此)开始。

2)它的复杂性是什么？答案:第一个循环完全遍历字符串，所以它至少是 O(n)，第二个循环仅在找到 start char 时执行，甚至部分(找到 start 的索引 + 1)。虽然，大 O 是最坏的情况，不是吗？所以在最坏的情况下，start 是第一个字符，内部迭代在字符串上迭代 n-1 次，-1 是一个常数，所以它是 n。但是，从统计上讲，内循环不会在每次外迭代时都执行，但由于大 O 大约是最坏的情况， 说它的复杂度是 O(n^2) 是否正确？ ?忽略任何常量以及在 99.99% 的情况下内循环不会执行每个外循环传递的事实。

3) 重写它以降低复杂性。
我不确定的是 start 最多发生一次 或者更多，如果最多一次，那么可以使用一个循环重写方法(具有指示是否遇到开始的标志，并从那里开始在每次结束时增加计数)，产生 的复杂性。 O(n) .

但以防万一，该开始可以出现多次，即 很可能是 ，因为作业是一门 Java 类(class)，我认为它们不会造成如此歧义。
在这种情况下，不可能使用一个循环来解决... 等待 !是的..!
只需有一个变量，例如，每次遇到 start 时都会增加 inc 并用于在找到第一个开始后每次遇到 end 时增加计数:

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

这也会产生 的复杂性O(n) ?因为只有1个循环。

是的，我意识到我写了很多呵呵，但我也意识到，通过将我的想法变成文字，我的理解会更好......

Answer 1

在任何给定的开始之后，它为每个结束字符增加 `count`。因此，如果有多个开始，它可以为同一结束多次增加它。

在最坏的情况下，它会调用 charAt (n^2 - n)/2 = ((n - 1) + (n - 2) + ... + 1) 次。即 O(n^2)。这发生在每个字符开始时。

如果你在第一次开始后计算结束字符，你可以简单地在内部 for 之后返回计数。但是由于计数递增的次数取决于启动次数，因此您的最终伪代码是正确的。但是，您需要切换 ifs 的顺序以处理 start == end 的特殊情况。您也不需要检查 inc > 0。

inc = 0, count = 0

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

这在所有情况下都是 O(n)。