Team TripleFalcon. http://www.triplefalcon.com/

概要

 計算機科学関連の書物に、よく「この関数は O(n) である。」のような O の表現を突然見かけたりします。 これは、ビッグ・オー記法といって、表記を簡単にする工夫です。 議論を正確にして、かつわかりやすくするために積極的に行う略記です。

 省くことは不正確にする事とは違います。 ある関数の性質を説明するときに 2n とか 3n といった係数のちょっとした違いが結果にたいした影響を及ぼさないと知っているとき、係数の省略を考えたとします。 しかし、単に n と書いてしまうと不正確になってしまいます。この O(オー) には「係数が省かれているから忘れないでね。」という意味があると考えてください。 以下のような表現は特に良く見かけます。

 数値同士の場合、n<m のように不等号という表現があります。関数同士で同様に比較が出来たら便利でしょう。この記法は、関数同士の比較に用いられます。

Team TripleFalcon. http://www.triplefalcon.com/

定義

 nが整数であるとします。

 f(n)=O(g(n)) であるとは、整数 m と正の定数 c が存在して、n≧m である任意の n について f(n)≦cg(n) であることです。いいかえると、nが小さい有限個の例外と、nに依存しない定数の影響を除いて、 g(n) は常に f(n) より大きい、といいたいわけです。このとき、f(n) は オーダー g(n) であるといいます。

 (1) と (2) は一般的なオー記法の利用方法です。長ったらしい式を簡潔に表現しています。

 (3) は、間違いではありません。ビッグオー記法では、Oの関数のほうが、値の成長が速いことを示す表記ですから理にかなっています。(4)は、ビッグオー記法の目的である簡潔な表現には反しますが、間違いであるとはいいにくいです。

 オー記法は、個人的には f(n)∈O(g(n)) とか f(n) ⊆ O(g(n)) の方が表現として適切ではないかと思います。O(g(n)) は g(n) より成長の遅い関数の集まりですから、指し示しているものは明らかに集合です。 しかしながら、慣習として 19 世紀から定着してしまったためにいまさら変えるのも難しいのだそうです。だから、教科書によっては頭の中に時々不等号や部分集合の記号を補うように勧めているものもあります。

 オー記法に登場する 「等号」 は通常とは意味が少し異なるのです。ビッグオー記法では、右辺と左辺を安易に入れ替えてはなりません。

 n = O(n) = 2n ゆえに n=2n

 と導いてはいけないわけです。

Team TripleFalcon. http://www.triplefalcon.com/

O記法の計算

 以下は、任意の f(n) と g(n) について成立します。 c は定数です。

f(n) =O(f(n))

c・O(f(n)) = O(f(n))

O(O(f(n)) = O(f(n))

O(f(n))O(g(n))=O(f(n)g(n))

O(f(n)g(n))=f(n)O(g(n))

Team TripleFalcon. http://www.triplefalcon.com/

オーダー

 あるところに複数の金融業者がいます。彼らは、100万円の貸し出しに以下のような「利息」を要求しています。1ヶ月間お金を借りるなら、どの金融業者がよいでしょうか。

A金融 1日1万円
B金融 n日で 1000 n2)円
C金融 n日で 100 n3
D金融 n日で 2n
 

 ものは試しに、具体的に利息を代入してみましょうか。数日分の利息は、例えば以下のとおりです。D金融はどう見ても安く、A,B 金融は高いです。2週間しか借りないのなら、D金融が一番いいに決まってます。

返済 A金融 B金融 C金融 D金融
1日 10000 1000 100 2
2日 20000 4000 800 4
3日 30000 9000 2700 8

 では一ヵ月後にどうなっているかというと・・・

返済 A金融 B金融 C金融 D金融
31日 31万 96万 298万 21億

 まあ、中学生でも簡単にだまされることはないとは思いますが、意外と、n2 と 2n の増え方の違いを意識しない大人もいるようです。もし、上記金融業者の違いを説明しようとした場合、利息がいくらであるかというような金額で説明するよりも利息の増え方を説明するほうがよい場合があります。このような金額の増え方を以下のように呼び表します。

 A,B,C 金融型の数値の増え方を多項式型増加といい、D金融型の数値の増え方を指数型増加といいます。また、A金融のような場合は、線形型増加と呼ぶこともあります。

A,B,C金融 D金融
増加型 多項式型 指数型

 多項式型増加に比べると、指数型増加ははるかに伸び率が高いのに驚きます。実は、多項式型増加であっても n1000 等という増加は感覚を麻痺させるのに十分なスピードで伸びますが、やがて指数型増加に追い抜かされます。多項式型増加は、どんなに恐ろしいものを考えても(せいぜい有限個の例外を除けば)指数型増加には負けてしまいます。

 つまり、金融業者を選別する場合は、1日目の利息のような具体的数値に目を向けるより、増加のスピードに着目したほうがいい場合が多いというわけです。そしてそれは、多項式型増加か、指数型増加かという型を基準にすればよいわけです。

 もし、A,B,C,D金融の n日返済の利息を ma(n),mb(n),mc(n),md(n) と表すと、nが限りなく大きくなれば必ず、 md(n) > mc(n) > mb(n) > ma(n) になります。

このような場合は、次のように係数を考えない記法のほうが現実をよく表すわけです。

A金融 B金融 C金融 D金融
増加型 多項式型 多項式型 多項式型 指数型
関数 10000 n 1000 n2 100 n3 2n
オーダー O(n) O(n2) O(n3) O(2n)

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

オー・記法(O notation)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール