Большая Сложность O метода
У меня есть этот метод:
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), второй цикл выполняется, только если запускаются, символ найден и даже затем частично (индекс, в котором запуск был найден + 1). Хотя, большой O - все о худшем случае нет? Таким образом в худшем случае, запуск является 1-м символом, и внутреннее повторение выполняет итерации по строке n-1 времен, эти-1 константа, таким образом, это - n. Но, внутренний цикл не будет выполняться каждая внешняя итеративная передача, статистически, но так как большой O о худшем случае, это корректно, чтобы сказать, что сложность его является O (n^2)? Игнорирование любых констант и того, что в 99,99% времен внутренний цикл не выполнит каждую передачу внешнего цикла.
3) Перепишите его так, чтобы сложность была ниже.
То, в чем я не уверен, - запускаются ли, происходит самое большее однажды или больше, если однажды самое большее, то метод может быть переписан с помощью одного цикла (имеющий флаг, указывающий, запускаются ли, был встречен и оттуда при постепенном увеличении количества при каждом возникновении конца), приводя к сложности O (n).
В случае, если, хотя, который запуск может появиться многократно, который, скорее всего, это, потому что присвоение имеет курс Java и я не думаю, что они сделали бы такую неоднозначность.
Решение, в этом случае, не является возможным использованием одного цикла... ОЖИДАЙТЕ! Да это..!
Просто имейте переменную, скажем, inc, чтобы быть увеличенными каждый раз, когда с запуском встречаются и используют для постепенного увеличения количества каждый раз, когда с концом встречаются после того, как 1-й запуск был найден:
inc = 0, count = 0
if (current char == start) inc++
if (inc > 0 && current char == end) count += inc
Это также привело бы к сложности O (n)? Поскольку существует только 1 цикл.
Да я понимаю, что записал много hehe, но что я также понял, то, что я понимаю намного лучше путем формирования моих мыслей в слова...
3 ответа
- Он увеличивает `count` для каждого конечного символа после любого заданного начала. Таким образом, если есть более одного начала, он может увеличивать его более одного раза для одного и того же конца.
- В худшем случае, он вызовет charAt (n^2 - n) / 2 = ((n - 1) + (n - 2) + ... + 1) раз. То есть O(n^2). Это происходит, когда каждый символ является стартовым.
- Если бы вы считали конечные символы после первого начального, вы могли бы просто вернуть count после внутреннего for. Но поскольку количество раз, на которое увеличивается счетчик, зависит от количества стартов, ваш окончательный псевдокод находится на правильном пути. Однако вам нужно изменить порядок ifs, чтобы справиться с особым случаем, когда start == end. Вам также не нужно проверять, что inc > 0.
inc = 0, count = 0
if (current char == end) count += inc
if (current char == start) inc++
Это O(n) во всех случаях.
- Как уже отметил Мэтью, сложность оригинального метода составляет O(n2)
- Ваш второй подход не является правильным, оригинальный метод, похоже, подсчитывает все подстроки, начинающиеся с begin и заканчивающиеся end, которые также могут содержать либо start, либо end.
- Это можно сделать за O(n), просто найти все начала, все концы, а затем выполнить итерации над двумя списками, перемещая указатели соответствующим образом.
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;
}