page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_cb
估算计算量
問題文
在下面的程序中,定义了六个函数f0到f5并从主函数调用。 估计每个函数的计算量,并注释掉调用花费最多计算时间的函数的行。
时间限制为 2 秒。 AtCoder 法官每秒 可以执行大约10^8计算。如果答案不正确。
读取约束并估计每个函数的执行时间。
程序
#include <bits/stdc++.h>
using namespace std;
int f0(int N) {
return 1;
}
int f1(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
s++;
}
for (int i = 0; i < M; i++) {
s++;
}
return s;
}
int f2(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
int t = N;
int cnt = 0;
while (t > 0) {
cnt++;
t /= 2;
}
s += cnt;
}
return s;
}
int f3(int N) {
int s = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
s++;
}
}
return s;
}
int f4(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s += i + j;
}
}
return s;
}
int f5(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
s += i + j;
}
}
return s;
}
int main() {
int N, M;
cin >> N >> M;
int a0 = -1, a1 = -1, a2 = -1, a3 = -1, a4 = -1, a5 = -1;
// 計算量が最も大きいもの1つだけコメントアウトする
a0 = f0(N);
a1 = f1(N, M);
a2 = f2(N);
a3 = f3(N);
a4 = f4(N);
a5 = f5(N, M);
cout << "f0: " << a0 << endl;
cout << "f1: " << a1 << endl;
cout << "f2: " << a2 << endl;
cout << "f3: " << a3 << endl;
cout << "f4: " << a4 << endl;
cout << "f5: " << a5 << endl;
}
制約
- 0 \leq N \leq 10^6
- 0 \leq M \leq 10^2
回答例
这是如何回答的示例。
在此示例中
我已经注释掉了对f0的调用,但是f0是
它仅由O(1)所以这个答案不正确。
#include <bits/stdc++.h>
using namespace std;
int f0(int N) {
return 1;
}
int f1(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
s++;
}
for (int i = 0; i < M; i++) {
s++;
}
return s;
}
int f2(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
int t = N;
int cnt = 0;
while (t > 0) {
cnt++;
t /= 2;
}
s += cnt;
}
return s;
}
int f3(int N) {
int s = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
s++;
}
}
return s;
}
int f4(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s += i + j;
}
}
return s;
}
int f5(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
s += i + j;
}
}
return s;
}
int main() {
int N, M;
cin >> N >> M;
int a0 = -1, a1 = -1, a2 = -1, a3 = -1, a4 = -1, a5 = -1;
// 計算量が最も大きいもの1つだけコメントアウトする
// a0 = f0(N);
a1 = f1(N, M);
a2 = f2(N);
a3 = f3(N);
a4 = f4(N);
a5 = f5(N, M);
cout << "f0: " << a0 << endl;
cout << "f1: " << a1 << endl;
cout << "f2: " << a2 << endl;
cout << "f3: " << a3 << endl;
cout << "f4: " << a4 << endl;
cout << "f5: " << a5 << endl;
}
提示
点击打开提示
表示每个函数的计算量。 考虑
| 計算量 | |
|---|---|
f0 |
O(1) |
f1 |
O(N+M) |
f2 |
O(N \log N) |
f3 |
O(1) |
f4 |
O(N^2) |
f5 |
O(NM) |
N和M的大小并选择执行时间最长的一个。
测试输入/输出
仅当您编写的程序没有成为 AC 并且您不知道原因时,请参阅此内容。
单击查看测试输入/输出
测试输入 1
1000000 100
测试输出 1
f0: 1 f1: 1000100 f2: 20000000 f3: 9 f4: -1 f5: -1404227328
解答例
在观看之前一定要自己尝试一下问题。
点击查看示例答案
#include <bits/stdc++.h>
using namespace std;
int f0(int N) {
return 1;
}
int f1(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
s++;
}
for (int i = 0; i < M; i++) {
s++;
}
return s;
}
int f2(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
int t = N;
int cnt = 0;
while (t > 0) {
cnt++;
t /= 2;
}
s += cnt;
}
return s;
}
int f3(int N) {
int s = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
s++;
}
}
return s;
}
int f4(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s += i + j;
}
}
return s;
}
int f5(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
s += i + j;
}
}
return s;
}
int main() {
int N, M;
cin >> N >> M;
int a0 = -1, a1 = -1, a2 = -1, a3 = -1, a4 = -1, a5 = -1;
// 計算量が最も大きいもの1つだけコメントアウトする
a0 = f0(N);
a1 = f1(N, M);
a2 = f2(N);
a3 = f3(N);
// a4 = f4(N);
a5 = f5(N, M);
cout << "f0: " << a0 << endl;
cout << "f1: " << a1 << endl;
cout << "f2: " << a2 << endl;
cout << "f3: " << a3 << endl;
cout << "f4: " << a4 << endl;
cout << "f5: " << a5 << endl;
}