• トノイテ、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • コス、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • キラササホフ 、リケヤ、ッ。」

*フワシ。 [#o29f0dea]

#contents


*キラササホフヘマタ [#v105c342]

。。、「、ス靉キイフ、オ皃皃・ラ・・ー・鬣爨ャハ」ソ、「、テ、ソ、ネ、ュ。「、ス、、鬢ホス靉シス遉シィ、ケ[[・「・・エ・・コ・濔]、ャニア、ク、ヌ、「、、ネ、マクツ、鬢ハ、、。」、ウ、ホ、隍ヲ、ヒフワナェ、ャニア、ク、ヌ。「ーロ、ハ、テ、ソ・「・・エ・・コ・爨ヘム、、、ニ、、、・ラ・・ー・鬣爨ャ、「、テ、ソセケ遑「、ノ、ホ・ラ・・ー・鬣爨ャコヌ、筅隍、、ォ、ノセイチ、ケ、エス爨マイソ、ォ。「、゙、ソ、ノ、ホ、ー、鬢、、隍、、ォ、ネ、、、ヲフワーツ、ソウリナェ、ヒヘソ、ィ、ヘマタ、ャ。「''キラササホフヘマタ''、ヌ、「、。」


*キラササホフ [#l5e2be92]

。。''キラササホフ。ハcomputational complexity。ヒ''、ネ、マ。「[[・「・・エ・・コ・濔]、ホタュヌス、ホネ豕モ、ヒ、ェ、、、ニオメエムナェ、ハネステヌシワナル、ネ、キ、ニニウニ、オ、、ソ、ヌ、「、。」
。。''キラササホフ。ハcomputational complexity。ヒ''、ネ、マ。「・「・・エ・・コ・爨ホタュヌス、ホネ豕モ、ヒ、ェ、、、ニオメエムナェ、ハネステヌシワナル、ネ、キ、ニニウニ、オ、、ソ、ヌ、「、。」

-サエヨキラササホフ。ハtime complexity。ヒ
--・ラ・・ー・鬣爨ホシツケヤウォサマ、ォ、鮨ェホサ、゙、ヌ、ヒヘラ、キ、ソサエヨ、ノセイチ、ケ、、筅ホ。」
--テアス网ヒキラササホフ、ネ、、、テ、ソ、ネ、ュ、マ。「サエヨキラササホフ、サリ、ケ、ウ、ネ、ャツソ、、。」
-ホホー霍ラササホフ。ハspace complexity。ヒ
--・ラ・・ー・鬣爨ホシツケヤウォサマ、ォ、鮨ェホサ、゙、ヌ、ヒタヘュ、ケ、オュイアホホー陦ヲ・ユ・。・、・ホホー隍ホ、ウ、ネ。」

。。クイフ、ャニア、ク、ヌ、「、、ミサエヨキラササホフ、ャテサ、、・「・・エ・・コ・爨ャ、隍、。」
。。ニア、クキイフ、ャニタ、鬢、、ハ、鬢ミ。「サエヨキラササホフ、萸ホー霍ラササホフ、ャセョ、オ、、・「・・エ・・コ・爨ャ、隍、。」


**キラササホフ、ホオ皃睫 [#v0275744]

。。キラササホフ、トエ、ル、、ソ、皃ヒ、マ。「キイフ、ャスミ、、゙、ヌ、ヒシツケヤ、オ、、オ。ウ」クフソホ皃ホシホ爨ネシツケヤソ、オ皃皃ニ。「ウニフソホ皃ホスヘュサエヨ、、ォ、ア、ソ、筅ホ、ホマツ、オ皃皃、ミ。「ヘカ、ネ、キ、ニオ皃皃鬢、。」、キ、ォ、キ、ウ、ホハヒ。、タ、ネ。「・マ。シ・ノ・ヲ・ァ・「、茹ウ・・ム・、・鬢ホタュヌス、ヒコクアヲ、オ、、、ソ、皃ヒ。「・「・・エ・・コ・爨ホヒワシチナェ、ハホノ、キーュ、キ、ネステヌ、ケ、、ヒ、マノヤナャナ、ヌ、「、。」

。。、ス、ウ、ヌ。「・ラ・・ー・鬣狹讀ヌシツケヤ、オ、、ハク、ホイソ、トエ、ル、ニ。「キラササホフ、ホフワーツ、ネ、ケ、ハヒ。、ャシ隍鬢、。」


**チイカ眷ェ [#pf38455f]

。。キラササホフ、オ皃皃ホ网ネ、キ、ニ。「タキチテオコ、ネ2ハャテオコ、ケヘ、ィ、ニ、゚、。」

。。ヌロホT、ヒnクト、ホ・ヌ。シ・ソ、ャ、「、、筅ホ、ネ、キ、ニ。「フワナェ、ホ・ヌ。シ・ソx、タキチテオコ、ヌテオ、ケ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「コヌセョ1イ。「コヌツ輜イ、ホ・ュ。シ、ホネ豕モ、ヌフワナェ、ホ・ヌ。シ・ソ、ャクォ、ト、ォ、。」、隍テ、ニ。「コヌツ遉ヌ、穗イ、ヌクォ、ト、ア、鬢、。ハクォ、ト、ォ、鬢ハ、、、ウ、ネ、ャ、、ォ、、ソ、皃ヒ、筍「nイ、ホ・ュ。シ、ホネ豕モ、ャノャヘラ、ヌ、「、。ヒ。」ネ豕モ、ヒノャヘラ、ハ1イ、ホ・。シ・ラス靉、ホサエヨ、a。「・。シ・ラ、ヒエリキク、ホ、ハ、、ス靉サエヨ、t、ネ、ケ、、ミ。「テオコサエヨ、マn。゚a+t、ネ、ハ、。」、ウ、ウ、ヌ。「n、ススハャツ遉ュ、ッ、ケ、、ネ。「サエヨt、マフオサ、ヌ、ュ、、ー、鬢、セョ、オ、ッ、ハ、、ホ、ヌ。「タキチテオコ、ヒノャヘラ、ハキラサササエヨ、ホカ盻テヘ、マan。ハa、マトソ。ヒ、ネノス、オ、、。」

。。シ。、ヒヌロホT、ヒnイ、ホ・ヌ。シ・ソ、ャセコス遉ヒウハヌシ、オ、、ニ、、、、ネ、キ、ニ。「フワナェ、ホ・ヌ。シ・ソx、2ハャテオコ、ヌテオ、ケセケ遉ケヘ、ィ、ニ、゚、。」2ハャテオコヒ。、ヌ、マ。「ネ豕モ、ホ、ソ、皃ヒノャヘラ、ハ・。シ・ラス靉、ケヤ、ヲナル、ヒテオコネマーマ、ャn/2,n/4,。ト、ネネセハャ、ヒ、ハ、テ、ニ、、、ッ。」、隍テ、ニ。「&mimetex("\log_2 n");。ハセョソナターハイシタレ、セ螟イ。ヒイ、ホ・。シ・ラス靉、シツケヤ、ケ、、ネ。「テオコネマーマ、ャ1ーハイシ、ヒ、ハ、遙「ス靉、ャスェホサ、ケ、。」、ウ、ホセケ遑「1イ、ホ・。シ・ラス靉、ヌノャヘラ、ハサエヨ、b、ネ、ケ、、ミ。「テオコサエヨ、マ&mimetex("b \times \log_2 n");。ハb、マトソ。ヒ、ネノス、サ、。」

。。ホセシヤ、ホキラサササエヨ、ヒ、ェ、ア、a,b、マCPU、茹ラ・・ー・鬣爨ホ・ウ・・ム・、・鬢ホタュヌス、ヒーヘツク、キ、ニハム、、、ャ。「n、マス靉ニ簣ニ、タ、ア、ヒーヘツク、ケ、。」、隍テ、ニ。「タキチテオコ、ホキラサササエヨ、マn。「2ハャテオコ、ホス靉サエヨ、マ&mimetex("\log_2 n");、ヒネ賽网ケ、、ネ、、、ィ、。」

。。、ウ、ホn、ホテヘ、マ。「フ萃熙ホツ遉ュ、オ、ノス、ケ・ム・鬣癸シ・ソ。シ、ヌ、「、テ、ソ。」キラササホフ、オ皃皃、ヒ、マ。「キラサササエヨ、ホ、ヲ、チ。「、ウ、ホn、ヒネ賽网キ、ニコヌ、篦ョ、ッキラサササエヨ、ャチイテ、ケ、ケ爨タ、ア、ヒテ衫ワ、キ、ニ。「、ス、ホツセ、マフオサ、ケ、。」、ト、゙、遙「n「ェ。遉ネ、キ、ニ。「n、ホコヌ、篦遉ュ、、シ。ソ、ホケ爨タ、ア、クォ、。ハキクソ、篶オサ、オ、、。ヒ、ホ、ヌ、「、。」、ウ、ホ、隍ヲ、ハ。「n「ェ。遉ネ、キ、ソ、ネ、ュ、ホキラササホフ、ホハムイス、。「キラササホフ、ホチイカ眷ェ、ハソカ、ノ、、、ネ、、、ヲ。」


**コヌツ邱ラササホフ。ヲハソカムキラササホフ。ヲチイカ眷ェキラササホフ [#y28feb7c]

-コヌツ邱ラササホフ。ハworst case complexity。ヒ
--コヌーュ、ホセケ遉ャニホマ、オ、、ソ、ネ、ュ、ホキラササホフ。」
-ハソカムキラササホフ。ハaverage case complexity。ヒ
--、ケ、ル、ニ、ホイトヌスタュ、ホニホマ、ャ、「、テ、ソ、ネ、ュ、ホハソカム、ホキラササホフ。」
-チイカ眷ェキラササホフ。ハasymptotic complexity。ヒ
--シ醢ラケ爨ホ、゚、ヌカ盻、キ、ソキラササホフ。」

。。キラササホフ、トエ、ル、、ネ、ュ。「コヌツ邱ラササホフ、隍熙簗ソカムキラササホフ、サネ、ヲセケ遉ャツソ、、。」コヌーュ、ホセケ遉ャカヒ、皃ニト网、ウホホィ、ヌ、キ、ォオッ、ュ、ハ、、セケ遉マ。「コヌツ邱ラササホフ、スナサ、キ、ハ、、ハ、ャクスシツナェ、ヌ、マ、ハ、、、ォ、鬢ヌ、「、。」


*チイカ眷ェキラササホフノセイチ [#qad7c56c]

。。・「・・エ・・コ・爨ホキラササホフ、ホ、ェ、ア、クキフゥ、オ、オュケ讀ホテ讀ヒハト、クケ、皃、ソ、皃ホ、筅ホ、ヌ、「、。」キラササホフ、ホセ蟶ツ、茣シクツ、ハ、ノ、ノス、ケ、ネ、ュ、ヒヘム、、、。」、隍ッサネ、、、、ホ、マシ。、ヒシィ、ケOオュヒ。、ネ、、、ヲ、筅ホ、ヌ、「、。」

**Oオュヒ。 [#hea42ccc]

。。''Oオュヒ。。ハO-notation。ヒ''、ネ、マ。「・「・・エ・・コ・爨ホキラササホフ、ノス、ケハヒ。、ホ、メ、ネ、ト、ヌ、「、。」、ウ、、マフ萃熙ホ・オ・、・コ、ツ遉ュ、ッ、キ、ニ、、、テ、ソ、ネ、ュ、ホチイカ眷ェキラササホフ、シィ、ケ、筅ホ、ヌ、「、。」O、マ''・ェ。シ・タ。シ''、ネ、、、ヲ。」キラササホフ、ホセ蟶ツ、ノス、ケセケ遉ヒヘュク、ヌ、「、。」

[トオチ]~
&mimetex("n \in \mathbb{Z}_{\ge 0}");~
&mimetex("g(n),f(n)");。ァn、ホエリソ~
、ネ、ケ、。」~
、ウ、ホ、ネ、ュ。「シ。、ホ、隍ヲ、ヒf、ホスクケ遉Oオュヒ。、サネ、テ、ニトオチ、オ、、。」~
&mimetex("O(g(n)):=\{ f(n) | \exists c,n_{0} \in \mathbb{R}_{>0} \, s.t. \, \forall n \ge n_0 , 0 \le f(n) \le c \cdot g(n) \}");

#img(http://security2600.sakura.ne.jp/main2/image2/O1.jpg)
#img(,clear)

[ハ荵ヨ1]&mimetex("O(g(n))");、マ。ヨ・ェ。シ・タ。シ・ェ・ヨ・ク。シ・ィ・フ。ラ、ネクニ、ヨ。」

[ハ荵ヨ2]・ソ。シ・イ・テ・ネ。ハシ醂。ヒ、マf(x)、ヌ、「、。」

ホ1。ァ&mimetex("a_2 n^2 + a_1 n + a_0 \in O(n^2)");

ホ2。ァ&mimetex("a_1 n + a_0 \in O(n^2)");

#img(http://security2600.sakura.ne.jp/main2/image2/O2.jpg)
#img(,clear)


***・ェ。シ・タ。シ、ヒエリ、ケ、チイテホィ、ホツ遉ュ、オ [#ec7366b3]

&mimetex("O(1)<O(\log n)<O(n)<O(n \log n)<O(n^c)<<O(n!)");


***ツ衙スナェ、ハ・「・・エ・・コ・爨ホサエヨキラササホフ [#p89d9aaa]

-&mimetex("O(1)");
--・マ・テ・キ・衢。。ハ・キ・ホ・ヒ・爨ハ、キ。ヒ
-&mimetex("O(m+n)");
--BMヒ。
-&mimetex("O(\log n)");
--2ハャテオコヒ。
-&mimetex("O(n)");
--タキチテオコヒ。
-&mimetex("O(n \log n)");
--・゙。シ・ク・ス。シ・ネ。「・ッ・、・テ・ッ・ス。シ・ネ。「・メ。シ・ラ・ス。シ・ネ
-&mimetex("O(mn)");
--テアス羸ネイヒ。
-&mimetex("O(n^{\frac{3}{2}})");
--・キ・ァ・・ス。シ・ネ
-&mimetex("O(n^2)");
--・ミ・ヨ・・ス。シ・ネ。「ヂニ・ス。シ・ネ。「タマネ・ス。シ・ネ。「・ッ・、・テ・ッ・ス。シ・ネ。ハコヌーュサ。ヒ


**Oオュヒ。ーハウー、ホチイカ眷ェキラササホフノセイチ [#n3f638e5]

[トオチ]~
&mimetex("\Omega(g(n)):=\{ f(n) | \exists c,n_{0} \in \mathbb{R}_{>0} \, s.t. \, \forall n \ge n_0 , 0 \le c \cdot g(n) \le f(n) \}");

#img(http://security2600.sakura.ne.jp/main2/image2/Omega1.jpg)
#img(,clear)

[トオチ]~
&mimetex("\Theta(g(n)):=\{ f(n) | \exists c_1,c_2,n_{0} \in \mathbb{R}_{>0} \, s.t. \, \forall n \ge n_0 , 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \}");

。。・「・・エ・・コ・爨ホヒワ、マOノスオュ、サネ、テ、ニ、、、、ウ、ネ、ャツソ、、、ャ。「ヒワナ、マヲィオュヒ。、ヘヘム、キ、ソ、ロ、ヲ、ャ、隍、。」ヘヘウ、ネ、キ、ニ。「O、マf、ホタュシチ、ノス、キ、ニ、、、、ネ、マクツ、鬢ハ、、、ネ、、、ヲナタ、ネ。「エェー网、。ヲエヨー网、、荀ケ、、、ネ、、、ヲナタ、ャオ、イ、鬢、、ォ、鬢ヌ、「、。」

。。Oオュヒ。、ヘヘム、ケ、、ネ。「シ。、ホ、隍ヲ、ヒ1シ。エリソ、&mimetex("O(n^2)");、ヒエ゙、゙、、。」

&mimetex("n \in O(n^2)");

。。、ウ、ホ、隍ヲ、ヒO、マf(n)=n、フタウホ、ヒノスクス、キ、ニ、、、ハ、、。ハチーシヤ、ホヘヘウ。ヒ。」、ス、ウ、ヌシ。、ホ、隍ヲ、ヒヲィオュヒ。、ヘヘム、ケ、、ミ1シ。エリソ、マ&mimetex("\Theta(n^2)");、ヒエ゙、゙、、ハ、、。」

&mimetex("n \not\in \Theta(n^2)");

。。、゙、ソ。「シ。、ホエリキクシー、マタョホゥ、キ、ハ、、。ハク蠑ヤ、ホヘヘウ。ヒ。」

&mimetex("n \in O(n^2) \Rightarrow \frac{1}{n} \in O(\frac{1}{n^2})");

。。、ハ、シ、ハ、鬢ミ。「フー、ホタ隍ホエリキク、マ&mimetex("\frac{1}{n} \le c \dots \frac{1}{n^2}");、ーユフ」、キ。「&mimetex("c \ge n");、ャタョ、ホゥ、チ。「c、マトソ、ヌ、ハ、ッ、ハ、。」、ウ、、マフキス筅ヌ、「、。」


**ノスクスハヒ。、ホエハハリイス [#cef01c96]

。。O(。ヲ),ヲク(。ヲ),ヲィ(。ヲ)、マ。「スクケ遉タ、ネ、、ォ、テ、ソセ螟ヌ。「シ。、ホ、隍ヲ、ヒス、ッ、ウ、ネ、筅「、。」

&mimetex("f(n) \in O(g(n)) \Longleftrightarrow f\(n)=O(g(n))");

ホ1。ァ&mimetex("T(n)=a_2 n^2 +O(n)");

ホ2。ァ&mimetex("O(f)+O(g)=O(f+g)");


*サイケヘハクク・ [#da11a1ea]

-ケヨオチ・ホ。シ・ネ
-。リ・ス・ユ・ネ・ヲ・ァ・「ウォネッオサスムシヤ。。ケ邉ハ・ィ・テ・サ・・キ・罕・マ・・ノ・ヨ・テ・ッ。ル
-。リ・ス・ユ・ネ・ヲ・ァ・「ウォネッオサスムシヤサクウツミコ。。・ウ・・ヤ・蝪シ・ソ・オ・、・ィ・・ケハ萃ュサホチ。ワク盧螻鮨ャフ萃遙ル


*・・・ッ [#yd8083e0]

-[[MathWorld:http://mathworld.wolfram.com/]]