HENAUOJ

B3Q发现新生大都不明白时间复杂的概念和其对做题的帮助，于是出了一道题来科普时间复杂度

时间复杂度就是用来方便程序员估算出程序的运行时间

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项系数存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

eg1：

// 计算Func3的时间复杂度
void Func3(int N, int M)
{
int count = 0;

//对于下面循环最多执行m次

for (int k = 0; k < M; ++k)
{
++count;
}

//对于下面循环最多执行n次

for (int k = 0; k < N; ++k)
{
++count;
}
printf("%d\n", count);
}

//总时间复杂度为O(N+M)

eg2：

//第一重循环最多执行M次

//第二重循换最多执行N次

//总复杂度最高为O(M*N)

for (int k = 0; k < M; ++k)
{
for (int j = 0; j < N; ++j)
{
++count;
}
}

[算法的时间与空间复杂度（一看就懂） - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/50479555)

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 1e7~1e8 为最佳，

同时一般的oj(在线评测平台)一秒能计算的次数为1e7~1e8

注意：每场题目所用算法以题目要求为准

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
仅供参考!!!!

n<=30 可以采用指数级别的算法如 dfs

n<=100 可以采用O(n^3)的算法如动态规划(dp)

n<=1000 可以才用O(n^2)的算法如 dp 二分

n<=10000 可以采用O(n*根号n)的算法如分块

n<=100000 可以采用O(n*log(n))的算法如sort等各种排序算法二分

n<=1000000 可以采用O(n)的算法如单调队列双指针

n<=10000000 可以采用O(根号n)的算法如判断质数

n<=1e18 可以采用O(log(n))的算法如最大公约数快速幂

现在给你一个n根据判断在上面给出的范围判断，应该使用什么复杂度的算法
为了符合签到题身份，B3Q决定给每个范围后面的一段中文替换成一个小写字母
其中：
d: 可以采用O(n*log(n))的算法如sort等各种排序算法二分
c: 可以采用O(n^3)的算法如动态规划(dp)
f: 可以采用O(log(n))的算法如最大公约数快速幂
h: 可以采用O(n)的算法如单调队列双指针
g: 可以采用O(根号n)的算法如判断质数
b: 可以才用O(n^2)的算法如 dp 二分
a：可以采用指数级别的算法如 dfs
e: 可以采用O(n*根号n)的算法如分块

问题 B: B3Q的时间复杂度

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

提示