オーダーについて知っておくべき5つのこと - わさっきhb

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

[paz3]

計算量を表すオーダーO(n)についての解説。入力数に対して最も高い次数、大きい値で表す。項の加算・定数倍は無視する。主要な順序は 定数(1) < logn < n < nlogn < n^2 < n^3 < 2^n < 3^n < n!

[msh514]

計算量　O表記

[crist18]

アルゴリズム見積もり

[takohaka]

"「アルゴリズムを改善する」とは，オーダーを小さくするようなアルゴリズムを見つけることと等価です．"

[Chisei]

ビッグオー記法

[hide98]

オーラー記法について

[witt]

アルゴリズム