Question

Дана строка длины n, состоящая из 0 и 1. Необходимо найти длину её наибольшей подстроки, состоящей только из 1. Например, для строки 101101001001111011 ответом является число 4 . Для решения данной задачи написана такая программа: #include #include #include using namespace std; int main() { string S; cin >> S; int n = S.size(); int ans = 0; for (int i = 0; i < n; ++i) { int t = 0; while (i < n && S[i] == '1') { ++t; ++i; } ans = max(ans, t); } cout << ans << endl; return 0; } Определите асимптотику данного алгоритма. O(1) O(log n) O(√n) O(n) O(n^2) Правильного ответа нет

Answer 1

Ответ: O(n)

Несмотря на то, что алгоритм имеет цикл в цикле сложность равняется O(n), так как оба цикла изменяют один и тот же счётчик на 1. И оба остановятся когда i будет равно n. То есть суммарно будет проделано n итераций.

Answer 2

Данный алгоритм имеет асимптотику O(n), так как он содержит один цикл, который проходит по всем символам входной строки, и внутри этого цикла выполняется операция поиска подстроки из единиц. Таким образом, время выполнения алгоритма линейно зависит от длины входной строки.