できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記

計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは

[kako-jun]

支配項の話は、nを無限にlimを計算する時に、最も次元の高い項以外を無視できるのと似てる。何か問題を解決する時に、もし改善できたら最も効果的な、支配的な要因以外を無視するのとも似てる

[crimsonstarroad]

労作。なるほどーと思いながら読みました。 計算量の話がトレンドになってから書いたわけじゃないとのこと。流石にそうだよね。

[sin-idea]

ビッグオーとスモールオー意識せずに書いて教員に意味わかってんの？って刺されるのは卒論発表までにやっておきたいですね

[tettekete37564]

全然分からない。俺たちは雰囲気でコードを書いてる。CPU命令を何個何回呼び出したか、効率よくキャッシュを使ってくれる様に使っているか、程度の認識。

[su_zu_ki_1010]

なるほどわからん。。。ソートの計算量の質問が出たらライブラリに任せていると答えるしかない。

[igni3]

それでO記法を正確な意味で使ってない人に会うたびにこの内容を説明するのですか？論文書く人ならまだしも、ほとんどの人に対しては私は嘘でも大雑把に説明しますよ。その方が平和だから。

[dorje2009]

いろんなソートアルゴリズムの速度を可視化した動画を久しぶりに見てみた https://www.youtube.com/watch?v=kPRA0W1kECg

[mozukuyummy]

これ、実は数3CのLimの話に絡むね。

[hatebu_ai]

だれも起点へのポインタを設置してないなら、せっかくだからこの青いブコメに貼り付けるぜ！ https://twitter.com/tome_ura/status/1448123878639874048

[nagatomo-beautiful55]

んちゃ

[a-kuma3]

お腹いっぱい。美味しくいただきました。

[igrep]

お疲れ様です。

[mattn]

めっちゃ丁寧に解説してある。

[yamami78651]

わかりやすい

[mumei-0]

“Oは計算量とは限らないというのをとりあえず念押ししておきます。 ”

[nakamura-kenichi]

ロートルPGからしたら今時そんな事も覚えとかなあかんか？って話やな。で、そのクソおっそいメソッドは計算量を最適化した結果のロジックで組んだんかいな？そっちは期日とっくに過ぎてもまだ組み上がってないがな。

[azzr]

これ、CS系学部卒なら全員知ってるはずの基本事項だよね。

[omega314]

ちゃんとしてる。

[letsspeak]

このタイミングでまとめ直してくれていてとてもありがたや

[diffie]

全体的に「へ～知らんかった」って感じなんだけど、もしかしたら大学でオペレーションズリサーチとかで習ってて、全て忘れてしまっただけなのかしら。

[t_f_m]

書きたいことを書く能力と伝えたいことを書く能力って別なんだよな……

[Windymelt]

おもしろかった

[nekonyantaro]

「競技プログラミング」というのがあるのか。日本人（というかアメリカ人か？）、なんでも競争にするの好きという印象。

[upran]

こういうのできる人って、出身大学でいうとどれくらいなんだろう。

[eru01]

ようこんだけ書いたなｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ計算量の見積もり実際めんどくせえので、雑に組むとき用に$表記マジで全言語に導入して欲しい

[n314]

むずい

[securecat]

全く全然理解できない。数学脳が脳内に1ミリもない…

[anus3710223]

イマジナリーコメント想定できるのすごい

[notepc-5522]

ウチの息子は小学校一年生だけど、もうプログラムの授業があります。この記事を読ませよう。

[aceraceae]

100日後案件

[daira4000]

知らない事多かったのでありがたい

[RySa]

コーヒー飲んで帰ってくる間にこの処理終わるように高速化してって言われるのが実世界。

[theta]

あの漫画、みんな見てんのか。影響力すごい。プログラムなんか書かずにまんが描いた方が良いな！

[mag-x]

え、はてブは今、計算量ブームなの？すげぇ。

[hiby]

数学オタクって感じで良いわ。

[odakaho]

“O(f(n)) を指して” “英語では f(n) は f of n と読むので、big-O of f of n と読んだりする”