#P1044. 时间复杂度
时间复杂度
复杂度判断
今天面条老师给大家讲解了算法复杂度(也可称为时间复杂度)的计算,并布置了作业题。面条老师在一个程序中写了很多个 for 循环,每一个 for 循环都是形如 for(int i = 1; i <= n; i++)
,且中间没有 continue,break 等影响循环执行的语句,即每一个 for 都会运行 n 轮(注意,并不是每一个循环里面定义的变量都叫 i,但是这个循环变量一定是从 1 到 n,执行 n 次)。现在面条老师想知道,他写的这个程序的算法复杂度是 n 的几次方。
在本题中,你可以将“算法复杂度”理解为“for循环最多嵌套的层数”。
输入描述
输入一个长度为 2n 的字符串,字符串的内容只可能是 0 或者 1,且 0 和 1 的数量相等。0 代表一个 for 循环的开始,1 代表一个 for 循环的结束。保证字符串合法。
输出描述
输出一行一个整数代表这个程序的算法复杂度是 n 的多少次方。
001101
2
010101
1
解释:
样例 1 中,最多有两层循环嵌套,即 0011
,所以算法复杂度是 n²,所以输出 2。
将样例 1 转化为代码即为:
for (int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
}
}
for (int i = 1; i <= n; i++)
{
}
样例 2 中,最多有一层循环嵌套,所以输出 1。
数据范围
对于 40% 的数据,有
对于 100% 的数据范围,有