できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
2つの期間が重なり合うかどうかを判定する。 - こせきの技術日記
2つの期間 A〜B と X〜Y が重なっているかどうかを判定したい場合。 のように4つのパターンがある。これを単純に、 A <= X && Y <= B || X <= A && Y <= B || A <= X && B <= Y || X <= A && B <= Yのように判定してはいけない。 Xは青い線の上を、Yは赤い線の上を動くとき、A〜B と X〜Y は重なり合う。この条件は、 X <= B && A <= Yこれで4つのパターンをカバーできる。ORは不要。始点と終点をわかりやすく書くと以下になる。 始点2 <= 終点1 && 始点1 <= 終点2アルゴリズムに名前がありそうな気がするけど、見つけられなかった。 (追記) 矩形の重なり判定の方が情報が見つかった。 * Life is beautiful: ビル・ゲイツの面接試験－私の場合 * 長方形の重なりを判定する問題 - ザ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムビジュアル大事典
