大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)它在做什么？答案:计算EACH之后的终止事件总数(或者是否？在指配中未指定,第3点取决于此)启动.

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

3)重写它以降低复杂性.
什么我不知道的是,是否开始出现最多一次以上,如果一旦最多,那么方法可以使用一个循环(有标记,指示是否重写开始已经遇到并从那里递增计数在每月底发生),产生O(n)的复杂性.

但是,如果这个开始可能出现多次,这很可能是因为赋值是Java课程,我认为它们不会产生这种模糊性.
在这种情况下,解决是不可能使用一个循环... 等待!是的..!
只要有一个变量,也就是说,公司将递增,每次启动时遇到与用于递增计数每次结束第1后遇到启动发现:

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

这也会产生O(n)的复杂性？因为只有一个循环.

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

Answer 1

1. 它会在任何给定的开始之后为每个结束字符增加“count”。因此，如果有多个开始，它可以为同一结束多次增加它。
2. 在最坏的情况下，它将调用 charAt (n^2 - n) / 2 = ((n - 1) + (n - 2) + ... + 1) 次。即 O(n^2)。当每个角色开始时都会发生这种情况。
3. 如果您在第一次开始后计算结束字符，则可以简单地在内部 for 之后返回计数。但由于计数增加的次数取决于启动次数，因此您的最终伪代码处于正确的轨道上。但是，您需要切换 if 的顺序来处理 start == end 的特殊情况。您也不需要检查 inc > 0。

inc = 0, count = 0

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

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