、ウ、ホ・レ。シ・ク、、マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、爨マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ 、ウ、ホ・レ。シ・ク、livedoor ・ッ・・テ・ラ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、瀝ivedoor ・ッ・・テ・ラ

フワシ。

キラササホフヘマタ

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

キラササホフ

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

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

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

キラササホフ、ホオ皃睫

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

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

チイカ眷ェ

。。キラササホフ、オ皃皃ホ网ネ、キ、ニ。「タキチテオコ、ネ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,。ト、ネネセハャ、ヒ、ハ、テ、ニ、、、ッ。」、隍テ、ニ。「\log_2~n。ハセョソナターハイシタレ、セ螟イ。ヒイ、ホ・。シ・ラス靉、シツケヤ、ケ、、ネ。「テオコネマーマ、ャ1ーハイシ、ヒ、ハ、遙「ス靉、ャスェホサ、ケ、。」、ウ、ホセケ遑「1イ、ホ・。シ・ラス靉、ヌノャヘラ、ハサエヨ、b、ネ、ケ、、ミ。「テオコサエヨ、マb~\times~\log_2~n。ハb、マトソ。ヒ、ネノス、サ、。」

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

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

コヌツ邱ラササホフ。ヲハソカムキラササホフ。ヲチイカ眷ェキラササホフ

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

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

チイカ眷ェキラササホフノセイチ

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

Oオュヒ。

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

[トオチ]
n~\in~\mathbb{Z}_{\ge~0}
g(n),f(n)。ァn、ホエリソ
、ネ、ケ、。」
、ウ、ホ、ネ、ュ。「シ。、ホ、隍ヲ、ヒf、ホスクケ遉Oオュヒ。、サネ、テ、ニトオチ、オ、、。」
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)~\}

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

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

ホ1。ァa_2~n^2~+~a_1~n~+~a_0~\in~O(n^2)

ホ2。ァa_1~n~+~a_0~\in~O(n^2)

・ェ。シ・タ。シ、ヒエリ、ケ、チイテホィ、ホツ遉ュ、オ

O(1)<O(\log~n)<O(n)<O(n~\log~n)<O(n^c)<<O(n!)

ツ衙スナェ、ハ・「・・エ・・コ・爨ホサエヨキラササホフ

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

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

[トオチ]
\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)~\}

[トオチ]
\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シ。エリソ、O(n^2)、ヒエ゙、゙、、。」

n~\in~O(n^2)

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

n~\not\in~\Theta(n^2)

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

n~\in~O(n^2)~\Rightarrow~\frac{1}{n}~\in~O(\frac{1}{n^2})

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

ノスクスハヒ。、ホエハハリイス

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

f(n)~\in~O(g(n))~\Longleftrightarrow~f\(n)=O(g(n))

ホ1。ァT(n)=a_2~n^2~+O(n)

ホ2。ァO(f)+O(g)=O(f+g)

サイケヘハクク・

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

・・・ッ