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