No.863 計算量

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 344
作問者 :

e869120 / テスター :

butsurizuki

5 ProblemId : 3315 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2019-08-16 14:05:42

E869120 君は、yukicoder にあるソースコードを提出しました。
その時、以下のような結果が出ました。

彼は計算量がちょうど

P * N

(

P

は自然数) 回の計算がかかるソースコードか、ちょうど

Q * N^{2}

(

Q

は自然数) 回の計算がかかるソースコードのいずれかを提出しました。
実行時間の情報から判断して、計算量が線形時間 (

P * N

回) であれば

1

を、

N^{2}

に比例するのであれば

2

と出力してください。
ただし、yukicoder のジャッジシステムは極めて安定的であるため、常に実行速度は変わらないものとします。

全ての入力データは以下の制約を満たします。

 $A$ 
 $B$

計算量が線形時間 ( $P * N$ 回) であれば $1$ を、 $N^{2}$ に比例するのであれば $2$ と出力してください。
最後に改行してください。

2
106

$N = 5 000$ の時に $2$ ミリ秒、 $N = 200 000$ の時に $106$ ミリ秒かかっているので、線形時間と考えるのが妥当でしょう。

77
124200

$N = 5 000$ の時に $77$ ミリ秒、 $N = 200 000$ の時に $124 200$ ミリ秒 ( $124.2$ 秒) かかっているので、 $N^{2}$ に比例する時間と考えるのが妥当でしょう。

2160000
86400000

普通ありえませんが、この提出はどうやら非常に定数倍の重い線形時間の解法らしいです。なぜでしょう？

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。