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 итераций.