すべての内容は以下の内容を参照して作成されています.

1.時間の複雑さ

質問する

質問です。

コンピュータは毎秒約3〜5億個の演算を処理することができる.
ただし、演算が単純な演算(ビットAND、OR、比較、加算など)なのか、複雑な演算(除算、乗算、代入、関数呼び出しなど)なのかは、回数によって異なる可能性があり、3-5億が推定値であることに注意してください.
このコードは何回演算するか考えてみましょう.
05行目に2つの変数を入力すると、06行目に2つの数字を追加し、出力時に演算する必要があります.これは通常3、4回の演算が必要です.したがって、1秒以内に、プログラムはすべてのコマンドを実行した後に完全に終了することができ、厳密には0.00001秒未満である.
では、今は時間の制限が何を教えてくれるかを感じることができるはずです.たとえば、時間が1秒に制限されている場合は、「プログラムは3～5億回の演算で答えを出して終了する必要があります」と説明します.

質問です。

まず02行目でcnt変数を宣言し、0を入れる過程で1行目、03行目でiの初期値に0を代入すると1、それからn回反復して03行目を見続け、iがn未満かどうかを決定し、n未満であれば1、演算を2回増やし、04行の5を除いた残りの部分を計算し、0と一致することを確認した場合、2回、5の倍数が1の場合、1つのcntを追加する必要があるため、1回計算し、最後のcntに戻る場合は、追加の計算が1回必要になります.
このように分解すると,この関数は5 n+3回の演算を必要とする.nが100万程度なら500万回程度、1秒で十分、nが10億なら50億回程度、1秒ではできない.

問題3-1

一番前からひとつずつ捕まえて「ガナダ」かどうか聞けばいい運が良ければ、聞くと探して、1秒、最悪の場合、「ガーナ」が最後なら全員に聞くので、N秒、平均で半分くらい聞けば「ガーナ」さんが見つかるので、N/2秒です.
そしてこのような時間がNに比例することが分かる人100名だと50秒くらいかかり、人が10倍増えると10倍の時間がかかり、500秒くらいかかります.

問題3-2

このように順番があればバックゲームのようにずっと仲介者に聞けばいいです最良の場合、最初に聞いた人が正しい場合、1秒かかります.最悪の場合、一人が残るまで、半分に割っていた場合、lg n秒、平均lg n秒です.所要時間はlg Nに比例した.

時間の複雑さ

入力サイズと問題解決に要する時間の相関

アルファベット

与えられた式を最大値の代表港を残す表現方法

예)
O(N) : 5N+3, 2N+10lgN, 10N
O(N²) : N²+2N+4, 6N²+20N+10lgN
O(NlgN) : NlgN+30N+10, 5NlgN+g
O(1) : 5, 16, 36

前述した「時間をNに比例させる」「lgNに比例させる」はbigoマーキング法で行われたことである.

｣時間複雑度比較パターン｣

一定時間O(1)が最も良く,次いでO(lgN),次いでO(N),O(NlgN),O(N)である.²) 明かりがついています.O(lgN)はログ時間、O(N)は線形時間、O(N)はO(lgN)からO(N)²)時間複雑度がlg nまたはnの乗算二乗の積である場合、多項式時間と呼ばれる.
O(2 N)は指数時間であり,Nが25以下に非常に小さくなければ,O(2 N)の解を必要とし,時間制限を通過することは困難である.O(N!)Nから!1~Nの積であり、N工場とも呼ばれる.

｣Nの大きさは時間の複雑さを許容する｣

例えば、所与のアレイをサイズ順に配列することを考慮すると、この問題はO(Nlgn)で解決することができ、O(N)²)を選択します.Nが1000未満の場合、どちらを書いても瞬く間に並べ替えが完了するが、Nが100万の場合、O(Nlgn)は1秒以内に並べ替えが完了し、O(N)は²)ソートが完了するまで、1時間近くかかります.

5천 이내 		👉🏻 O(N²)
100만 이내 	👉🏻 O(NlgN)
1000만 이내 	👉🏻 O(N) 
그 이상		👉🏻 O(lgN), O(1)

質問する

質問です。

for文では、iが1からNに移動し、3で5で除算されていることを確認します.時間的複雑度はO(N)

質問です。

最も簡単な方法は、デュアルfor文を使用して、すべての2対の合計が100であることを決定することです.O(N²)わかるよ

質問です。

i 1から2,3までこのように最大√Nまで歩き,時間複雑度はO(√N)である.

質問です。

Nが2 kより大きいか2 k+1より小さい場合、ゲートではvalを最大2倍に増大させることができる.valは2 kになり、2*val<=Nは嘘になるからです.したがって,Nが2 kまたは2 k+1未満の場合,時間複雑度はO(k)であり,ログ定義の観点からkはlgn,最終時間複雑度はO(lgn)である.

2.空間複雑度

入力のサイズと問題解決に必要な空間の相関
例えば、Nサイズの2次元アレイが必要な場合、O(N)²)タイルを必要としない場合はO(1)である.しかし,符号化試験では,空間複雑度問題に比べて時間複雑度問題が誤りやすい.スペースの複雑さはあまり気にしないでください

512MB = 1.2억개의 int

ただし、問題を解くときは、メモリが512 MBに制限されている場合、int変数を約1.2億個宣言できることを覚えておいてください.これはintが4バイトで計算できます.
これを覚えておくと、5億の大きさの配列が必要になると、エラーのプールであることにすぐに気づき、他のプールを考慮することができます.十分な手配をしてから気づいたら、濡れ衣を着せられた.