Question

Помогите пожалуйста, выполнить задание. Дана строка длины n, состоящая из 0 и 1. Необходимо найти длину её наибольшей подстроки, состоящей только из 1. Например, для строки 101101001001111011 ответом является число 4. Для решения данной задачи написана такая программа: S = input() n = len(S) ans = 0 i = 0 while i < n: t = 0 while i < n and S[i] == '1': i += 1 t += 1 ans = max(ans, t) i += 1 print(ans) Определите асимптотику данного алгоритма. 2 попытки O(1) O(logn) O(n−−√) O(n) O(n2) Правильного ответа нет

Answer 1

Ответ:

В файле все ответы на сириус

Объяснение:

Answer 2

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

Давайте разберемся, почему так происходит:

1. Программа считывает входную строку длины n.
2. Затем она начинает итерироваться по строке один раз, посимвольно.
3. Внутри внешнего цикла происходит вложенный цикл, который также итерируется по строке. Этот вложенный цикл будет иметь длину не более n, так как он прерывается, как только встречается символ '0' или достигнут конец строки.
4. Внутренний цикл на каждой итерации инкрементирует переменную t, представляющую длину текущей последовательности единиц.
5. После завершения внутреннего цикла программа обновляет переменную ans, которая хранит максимальную длину последовательности единиц, в случае, если текущая последовательность оказалась длиннее предыдущей максимальной.
6. Затем внешний цикл переходит к следующему символу и процесс повторяется.

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

Ответ: O(n)