hanaaaaaachiru https://blog.hatena.ne.jp/hanaaaaaachiru/ はなちるのマイノート https://www.hanachiru-blog.com/ 勉強メモ はじめに 今回はオーダー記法の定義について書いていきたいと思います。オーダー記法とは関数の値の発散の速さを漸近的に評価するものです。実用の仕方というよりはどのように定義をされているかという視点からみていきます。 はじめに O記法 Ω記法 Θ記法 多項式時間と超多項式時間 付録 O記法 O記法(ビックオー)は関数f(n) の発散のスピードは早くても g(n) と同じくらいという意味で用います。いわゆる関数の上界。 例：, (本来ならは集合なのでが正しいですが、=で書くことが多い) 条件を満たすような正定数を見つけられるかが一番の鍵となります。簡単な例を用いて、証明をしてみましょう。 関数がに含ま… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwww.hanachiru-blog.com%2Fentry%2F2020%2F05%2F31%2F120000" title="オーダー記法(O記法，Ω記法，Θ記法)の定義についてのメモ - はなちるのマイノート" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20f%28n%29%5Cin%20O%28g%28n%29%29%20%5CLeftrightarrow%20%E3%81%82%E3%82%8B2%E3%81%A4%E3%81%AE%E6%AD%A3%E5%AE%9A%E6%95%B0%20n_0%20%2Cc%E3%81%8C%E5%AD%98%E5%9C%A8%E3%81%97%EF%BC%8C%E5%85%A8%E3%81%A6%E3%81%AE%E6%95%B4%E6%95%B0n%20%5Cgeq%20n_0%20%E3%81%AB%E5%AF%BE%E3%81%97%E3%81%A6f%28n%29%20%5Cgeq%20c%20g%28n%29 Hatena Blog https://hatena.blog 2020-05-31 12:00:00 rich https://www.hanachiru-blog.com/entry/2020/05/31/120000 1.0 100%