http://metabolomics.jp/mediawiki/index.php?action=history&feed=atom&title=Aritalab%3ALecture%2FAlgorithm%2FBigO
Aritalab:Lecture/Algorithm/BigO - Revision history
2026-04-08T12:49:25Z
Revision history for this page on the wiki
MediaWiki 1.19.1
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/BigO&diff=254123&oldid=prev
Adm: moved Aritalab:Lecture/Basic/BigO to Aritalab:Lecture/Algorithm/BigO
2011-06-01T15:32:06Z
<p>moved <a href="/mediawiki/index.php?title=Aritalab:Lecture/Basic/BigO&action=edit&redlink=1" class="new" title="Aritalab:Lecture/Basic/BigO (page does not exist)">Aritalab:Lecture/Basic/BigO</a> to <a href="/wiki/Aritalab:Lecture/Algorithm/BigO" title="Aritalab:Lecture/Algorithm/BigO">Aritalab:Lecture/Algorithm/BigO</a></p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 15:32, 1 June 2011</td>
</tr></table>
Adm
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/BigO&diff=254122&oldid=prev
Adm at 03:01, 20 May 2011
2011-05-20T03:01:28Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 03:01, 20 May 2011</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>__FORCETOC__</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>__FORCETOC__</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">==まとめ==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* O記法は関数の上限を与える</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">: e.g. log ''n'' = O(''n'' )</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* &Omega;記法は関数の下限を与える</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">: e.g. ''n''<sup>2</sup> = &Omega;(''n'' )</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">* &Theta;記法はO記法と&Omega;記法をあわせたもの</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==O記法==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==O記法==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 13:</td>
<td colspan="2" class="diff-lineno">Line 19:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Omega;(g(x))</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Omega;(g(x))</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>と書きます。つまり、&Omega;<del class="diffchange diffchange-inline">記法は関数の加減を与えます。</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>と書きます。つまり、&Omega;<ins class="diffchange diffchange-inline">記法は関数の下限を与えます。</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==&Theta;記法==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==&Theta;記法==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義 &Theta;( )</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義 &Theta;( )</div></td></tr>
</table>
Adm
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/BigO&diff=254121&oldid=prev
Adm at 18:07, 7 November 2010
2010-11-07T18:07:01Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 18:07, 7 November 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>__FORCETOC__</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>__FORCETOC__</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==O記法==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==O記法==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>;定義 <del class="diffchange diffchange-inline">O( )</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>;定義</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) &le; c g(x) &nbsp; (&forall; x &ge; x<sub>0</sub>)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) &le; c g(x) &nbsp; (&forall; x &ge; x<sub>0</sub>)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = O(g(x))</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = O(g(x))</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">と書く。つまり、O記法は関数の上限を与える。</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">と書きます。つまり、O記法は関数の上限を与えます。</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">;定義 </del>&Omega;<del class="diffchange diffchange-inline">( )</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">==</ins>&Omega;<ins class="diffchange diffchange-inline">記法==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">;定義</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) &ge; c g(x) &nbsp; (&forall; x &ge; x<sub>0</sub>)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) &ge; c g(x) &nbsp; (&forall; x &ge; x<sub>0</sub>)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Omega;(g(x))</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Omega;(g(x))</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">と書く。つまり、</del>&Omega;<del class="diffchange diffchange-inline">記法は関数の加減を与える。</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">と書きます。つまり、</ins>&Omega;<ins class="diffchange diffchange-inline">記法は関数の加減を与えます。</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">==&Theta;記法==</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義 &Theta;( )</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義 &Theta;( )</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>関数 f(x) が</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>関数 f(x) が</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 18:</td>
<td colspan="2" class="diff-lineno">Line 20:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>を満たすならば</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Theta;(g(x))</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Theta;(g(x))</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">と書く。</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">と書きます。</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==注==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==注==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Ｏ、&Omega;、&Theta;記法で表しているのは関数の集合であるため、本当なら</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Ｏ、&Omega;、&Theta;記法で表しているのは関数の集合であるため、本当なら</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) &isin; O(n<sup>n</sup>)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) &isin; O(n<sup>n</sup>)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">のように書かなくてはならない。しかし、便宜的に</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">のように書かなくてはなりません。しかし、便宜的に</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: O(n) + O(n) = O(n)、や</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: O(n) + O(n) = O(n)、や</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = x<sup>2</sup> + O(n)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = x<sup>2</sup> + O(n)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">のように書くことが多い。</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">のように書くことが多いです。</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">また上の定義からは、</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">: log n = O(n)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">: n = O(n<sup>2</sup>)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">なのですが、このような書き方もほとんどせず、O記法を&Theta;のようにみなして書きます。</ins></div></td></tr>
</table>
Adm
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/BigO&diff=254120&oldid=prev
Adm at 05:28, 18 October 2010
2010-10-18T05:28:30Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 05:28, 18 October 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">__FORCETOC__</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==O記法==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==O記法==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義 O( )</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>;定義 O( )</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 18:</td>
<td colspan="2" class="diff-lineno">Line 19:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Theta;(g(x))</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>: f(x) = &Theta;(g(x))</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>と書く。</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>と書く。</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">==注==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">Ｏ、&Omega;、&Theta;記法で表しているのは関数の集合であるため、本当なら</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">: f(x) &isin; O(n<sup>n</sup>)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">のように書かなくてはならない。しかし、便宜的に</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">: O(n) + O(n) = O(n)、や</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">: f(x) = x<sup>2</sup> + O(n)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">のように書くことが多い。</ins></div></td></tr>
</table>
Adm
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/BigO&diff=254119&oldid=prev
Adm: New page: ==O記法== ;定義 O( ) 関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して : f(x) ≤ c g(x) (∀ x ≥ x<sub>0</sub>) を満たすならば : f(x) = O...
2010-10-18T05:09:15Z
<p>New page: ==O記法== ;定義 O( ) 関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して : f(x) ≤ c g(x) (∀ x ≥ x<sub>0</sub>) を満たすならば : f(x) = O...</p>
<p><b>New page</b></p><div>==O記法==<br />
;定義 O( )<br />
関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して<br />
: f(x) &le; c g(x) &nbsp; (&forall; x &ge; x<sub>0</sub>)<br />
を満たすならば<br />
: f(x) = O(g(x))<br />
と書く。つまり、O記法は関数の上限を与える。<br />
;定義 &Omega;( )<br />
関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して<br />
: f(x) &ge; c g(x) &nbsp; (&forall; x &ge; x<sub>0</sub>)<br />
を満たすならば<br />
: f(x) = &Omega;(g(x))<br />
と書く。つまり、&Omega;記法は関数の加減を与える。<br />
;定義 &Theta;( )<br />
関数 f(x) が<br />
: f(x) = O(g(x)), f(x) = &Omega;(g(x))<br />
を満たすならば<br />
: f(x) = &Theta;(g(x))<br />
と書く。</div>
Adm