Python 計算量の沼で元気にクロール＼(^o^)／
今日も今日とて、pythonのお勉強！
今日は、前回と前々回の反省を活かし、Atcoderのコンテストで【TLE】にならないように、計算量や実行時間のお勉強！学習に使用した参考文献は下記の記事
計算量とかいう未開の地
これまで、実行時間とか、計算量とか気にしたことなかったから、未開の地。先輩から
「for文の中にfor文を書くのはやめようね」
とは言われていたけど、、
ま、御託を並べてもしょうがないので、早速勉強！
参考文献
上記の記事によると、nのk次関数のｋの部分が実行時間や計算量に大きな影響を与えているっぽい。
だから、for文一回なら、O(n)だし、
for文の中にfor文を作るとO(n^2)ってなるってこと。
「なるほど・・・」
今まで、「for文の個数 ＝ 次数」だと思っていたけど、それは間違いだったみたい。
ここまではなんとか理解できました。
ですが、O(log(n))のところで躓きました・・
反復(i = i*2) のところがわからない・・・
ある程度、実行時間や計算量について理解できたのですが、反復(i = i*2) のところで躓きました・・・
記事に丁寧に書いたあったのですが、、うまく理解できませんでした(´；ω；｀)
記事によると、反復でかつ、i が定数倍のときは、O(log(n))になるんかな？
（↑自信ないので、間違っていたらコメント下さい。）
書いてあることは高校数学の範囲なので、式変形自体は理解できたのですが、なんでその式になるかがわからない。
よくわからないから別の記事を読んでみる
理解不足を埋めるため、他の記事も読んでみました。
上記の記事は、計算量について基本知識の記事でした。
上記の記事によると、問題で定義されている制約がTLEと深い関係があるっぽい
だから、制約よりも小さいk次関数なら大丈夫。
とりあえず、入力値のmaxが10^3くらいだったら、for文を二重にまわしても大丈夫ってことなんか？？？
わからん！！
足りないのは、事前知識と思考法
今までは、「解ければいいや」としか思ってなかったのですが、AtcoderのC問題以上になると、計算量についても思案しないとだめっぽい
これからは、問題文をみたら、「どーやったら解けるか」だけじゃなく、「計算量はいくつか」「どーやったら計算量を落とせるか」まで考える。
そのために必要なのは、計算量に関する事前知識と思考法が大事。
２記事ともすごく丁寧に説明されていたので、再度読み込みしていきたいと思います！
目指せ茶色！！
この記事が気に入ったらサポートをしてみませんか？