TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

02
 

よく忘れる計算量(随時更新)

【作成日】 2021/08/27 23:16  【更新日】 

いける?いけない?がパっとわかる表

\(N\) \(O(1)\) \(O(log \, N)\) \(O(N)\) \(O(N \, log \, N)\) \(O(N^{2})\) \(O(2^{N})\)
\(1\) 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
\(10\) 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
\(1000\) 一瞬 一瞬 一瞬 一瞬 およそ\(0.01\)秒 すごく長い
\(10^{6}\) 一瞬 一瞬 およそ\(0.01\)秒 およそ\(0.2\)秒 およそ\(3\)時間 すごく長い
\(10^{8}\) 一瞬 一瞬 およそ\(1\)秒 およそ\(30\)秒 およそ\(3\)年 すごく長い
\(10^{16}\) 一瞬 一瞬 およそ\(3\)年 およそ\(170\)年 すごく長い すごく長い

1,000,000 くらいだと安心。じゃぁ、どれくらいまでなら大丈夫なの?

\(A \leq 2,000,000,000\) でも、以下のような単純な処理だと間に合う。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long A;
  cin >> A;
 
  // 答え
  long long ans = 0;
 
  // 400で割り切れたらansに1加える 
  for (int i = 0; i <= A; ++i) {
    if (i % 400 == 0) {
      ans++;
    }
  }
 
  cout << ans << endl;
  return 0;
}

AtCoderの「C++入門 AtCoder Programming Guide for beginners (APG4b)」の「EX21 – 計算量の見積もり」では、計算量について以下のようにいっています。

(制限時間は2秒です。) AtCoderのジャッジでは1秒あたり\(10^{8} = 100,000,000\) 回程度の計算が可能です。

以下の問題は、\(N \leq 3000\) で、累積和を使って \(O(N^{2})\) になる問題ですが、間に合います(というか楽に間に合います)。

A – Abundant Resources
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

\(log \, N\) はどれくらい?

\(N = 200000\) のとき、 \(log \, N = 5.301….\) 。

したがって、実行時間制限が \(2\) 秒の場合、 \(N = 200000\) のとき、計算量は \(O(N \, log \, N)\) でも間に合います。

計算量が \(O(N \, log \, N)\) と言えば、

などがあります。