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 + t < n && S[i + t] == '1') ++t; ans = max(ans, t); } cout << ans << endl; return 0; } Определите асимптотику данного алгоритма. O(1) O(logn) O(√n) O(n) O(n^2) Правильного ответа нет

Answer 1

Ответ: O(n^2)

Два независимых цикла, один из которых вложенный, дадут именно квадратичную асимптотику

Answer 2

Асимптотика данного алгоритма - O(n), так как программа содержит один цикл, который проходит по строке длиной n и ищет подстроку из единиц. Каждая итерация цикла имеет сложность O(1), поэтому общая сложность алгоритма будет O(n).