研究室のゼミ発表で,「オーダーのことはよく分かっていませんが…」という前置きで計算量の見積もりをしているものを,昨年,今年と見かけました. この日記が役に立つか,余計な御世話になるか分かっていませんが,ここに整理を試みてみました. 1. ビッグ・オー記法 「アルゴリズムの計算量をオーダーで表してみなさい」と指示されたときのオーダーは, 注文,発注という意味でもなく, 順番*1,順序,秩序という意味でもなく, 「百万のオーダー」*2というような使い方でもなく, 数学の位数という意味でもなく, ビッグ・オー記法,あるいはwikipedia:ランダウの記号を用いて表すものを言います. 2. 一番次数の高いもの以外,それと係数は無視 ビッグ・オー記法では,基本的に,一つの文字に関するできるだけ簡単な数式に,「O( )」をかぶせます.このとき, 複数の項の足し算なら,次数の最も高いものだけを残し,他