Дана строка длины 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)
Правильного ответа нет
.
Для решения данной задачи написана такая программа:
#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)
Правильного ответа нет
More Questions From This User See All
Answers & Comments
Ответ: O(n)
Несмотря на то, что алгоритм имеет цикл в цикле сложность равняется O(n), так как оба цикла изменяют один и тот же счётчик на 1. И оба остановятся когда i будет равно n. То есть суммарно будет проделано n итераций.