Big 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) Что он делает? Ответ: подсчет общего числа end вхождений после EACH (или это? Не указано в назначении, от этого зависит пункт 3) start .

2) В чем его сложность? Ответ: первый цикл полностью перебирает строку, поэтому он равен по крайней мере O (n) , второй цикл выполняется только в том случае, если найдено start char и даже частично (индекс, при котором начало найдено + 1). Хотя, большой О это все о худшем случае нет? Таким образом, в худшем случае, start является первым символом, и внутренняя итерация повторяет строку n-1 раз, -1 является константой, поэтому n . Но статистически внутренний цикл не будет выполняться при каждом внешнем проходе итерации, но поскольку большой O соответствует наихудшему случаю, правильно ли говорить, что его сложность составляет O (n ^ 2) ? Игнорирование любых констант и тот факт, что в 99,99% случаев внутренний цикл не будет выполнять каждый проход внешнего цикла.

3) Перепишите его так, чтобы сложность была ниже.
Что я не уверен, так это то, происходит ли start самое большее один раз или больше, если самое большее один раз, то метод может быть переписан с использованием одного цикла (с флагом, указывающим, является ли встречается * начало и оттуда при увеличении счет в каждом конце вхождении), что приводит к сложности O (n) .

Однако, если start может появиться несколько раз, что , скорее всего, , потому что задание имеет курс Java, и я не думаю, что они сделают такую ​​двусмысленность .
Решение, в этом случае, невозможно с помощью одной петли ... WAIT ! Да, это так!!
Просто укажите переменную, скажем, inc , которая будет увеличиваться каждый раз, когда встречается начало , и используется для увеличения count каждый раз, когда встречается конец после того, как 1-е начало было найдено:

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

Это также приведет к сложности O (n) ? Потому что есть только 1 петля.

Да, я понимаю, что много написал, хе-хе, но я также понял, что гораздо лучше понимаю, превращая свои мысли в слова ...

Answer 1

1. Увеличивает `count` для каждого конечного символа после любого заданного начала. Так что, если есть более одного начала, он может увеличивать его более одного раза для одного и того же конца.
2. В худшем случае он вызовет charAt (n ^ 2 - n) / 2 = ((n - 1) + (n - 2) + ... + 1) раз. Это О (п ^ 2). Это происходит, когда каждый персонаж начинается.
3. Если вы подсчитывали конечные символы после первого запуска, вы могли бы просто вернуть счетчик после внутреннего for. Но так как количество раз увеличивается, зависит от количества запусков, ваш последний псевдо-код находится на правильном пути. Тем не менее, вам нужно изменить порядок ifs, чтобы иметь дело с особым случаем, где start == end. Вам также не нужно проверять, если inc> 0.

inc = 0, count = 0

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

Это O (n) во всех случаях.

Answer 2

• Как уже указывал Матфей, ​​сложность оригинального метода составляет O ( n ² )
• Ваш второй подход неверен, кажется, что оригинальный метод подсчитывает все подстроки, начиная с start и заканчивая end , который также может может содержать либо начало или конец .
• Это можно сделать в O ( n ), просто найти все начала, все концы, а затем перебрать два списка, перемещая указатели соответствующим образом.

Answer 3

1) Да.
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;
}