誰にも見えないブログ

雑なメモ。まとまってない文章等

今日のアルゴリズム:多項式、指数関数、対数関数、階乗

algorithm 勉強メモ

tex on はてブを諦めない。

多項式

  • 一般にp(n)=\sum_{i=0}^{d}a_in^iで表される関数をnに関するd次の多項式という

    • a_0,a_1,...a_d :多項式の係数(coefficient)
      • ただしa_d \neq 0
        • ※この制約はa_dが0のときn-1次の多項式になってしまうのを防ぐためにあるのだと思う。

    • p(n)=Θ(n^d)である

    • f(n)=O(n^k)のとき、関数f(n)は多項式的に限定されている(polynomially bounded)と言う

指数関数

  • 一般的にy=a^xで表される関数を指数関数という
    • \lim_{x \to \infty} \frac{n^b}{a^n}=0
      • 底が1より真に大きい任意の指数関数は多項式より早く増加する
        • (底=上記式のaのこと)
    • n^b=o(a^n)
    • 自然対数2.71828...=e
      • e^x=\sum_{i=0}^{∞}\frac{x^i}{i!}が成り立つ
      • e^x \geq 1+x
        • 補足:\sum_{i=0}^{∞}\frac{x^i}{i!}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...なので
      • 1+x \leq e^x \leq 1 + x + x^2 ただし|x| \leq 1
      • e^x=1+x+Θ(x^2)ただしx \to 0
      • \lim_{x \to ∞}(1+\frac{x}{n})^n=e^x
    • ※note:自然対数は紹介だけで、どうアルゴリズムに関係するかはまだ特に書かれていない。

対数関数

  • 二進数対数:\lg n = \log_2 n
  • 自然対数:\ln n=\log_e n
  • 冪乗:\lg ^kn=(\lg n)^k
  • 合成:\lg\lg n=\lg(\lg n)
  • 性質
    • a=b^{\log_{b}a}
      • 例(a=8,b=2):8=2^{\log_{2}8}
    • \log_c(ab)=\log_{c}a + \log_{c}b
      • 例(a=8,b=16,c=2):\log_{2}128=\log_{2}8 + log_{2}16
        • 7 = 3 + 4
    • \log_{b}a^n=n\log_{b}a
      • 例(a=16,b=2,c=2):\log_{2}16^2=2\log_{2}16
        • 8 = 2 * 4
    • \log_{b}a=\frac{\log_{c}a}{\log{c}b}
      • 例(a=16,b=4,c=2):\log_{4}16=\frac{\log_{2}16}{\log_{2}4}
      • 2=\frac{4}{2}
    • \log_{b}(1/a)=-\log_{b}a
      • 例(a=8,b=2):\log_{2}(1/8)=-\log_{2}8
        • memo:2^{-3}=1/8
    • \log_{b}a=\frac{1}{\log_{a}b}
      • 例(a-4,b=2):\log_{2}{4}=\frac{1}{\log_{4}{2}}
        • 4^{\frac{1}{2}}=\sqrt{4}=2
    • a^{\log_{b}c}=c^{\log_{b}a}
      • 例(a=2,b=4,c=256):2^{\log_{4}256}=256^{\log_{4}2}
        • 2^4=256^{\frac{1}{2}}
        • 16=16

※例は私が適当に検証したもの

  • 対数の底を別の定数に変えても対数の値は定数倍しか変化しないので定数因子が無視できるときはlgnを使うことが多い
  • f(n)=o(\lg^{k}n)であるとき関数f(n)は対数多項式的に限定されている(polylogarithmeicaally bounded)という
  • 任意の正の多項式関数はどんな対数多項式関数よりも早く増加する。

階乗

  • n!
    • n * (n-1) * (n-2) * ... * 1のような式のこと
    • 計算量
      • 上界:n!=o(n^n)
      • 下界:n!=ω(2^n)
      • 補足:上記二つは証明することが練習問題になってる
      • 他:\log_{2}(n!) = Θ(n \log_2{n})

反復

関数の反復適応

  • f^{(i)}(n):初期値nに対してf(n)をi回適用して得られる関数
  • 再帰的
    • f^{(i)}(n)=n :i=0の時
    • f^{(i)}(n)=f(f^{(i-1)}(n)):i>0の時
  • f(n)=2nであればf^{(i)}(n)=2^{i}n

反復対数関数

  • 対数関数を反復適用するもの。\lg^{*}nと表記する f:id:yuyubu:20200102105458p:plain
  • 定義:上記画像:tex\log^{*}n=\min\left\{i \geq0:\lg^{(i)}n \leq 1 \right\}がhatenablogでレンダできなかったので画像を貼っておく
    • 意味的には"1を下回る対数関数のi回の適用結果のうち、iが最小のもの"
      • 例:\lg^{*}16=3:16は\log_{2}nを反復適用すると4回目で1を下回るので\lg^{*}16の結果は3です。
        • 1回目:\log_{2}16=4
        • 2回目:\log_{2}{4}=2
        • 3回目:\log_{2}2=1
        • 4回目:\log_{2}1=0←1を下回った！
  • 非常にゆっくりと増加する。
    • 観測可能な宇宙の原子の個数推定10^{80}が2^{65536}よりずっと少ないため、\lg^{*}(2^{65536})=5以上の数値を超えることはほぼない。

フィボナッチ数

  • 0,1,1,2,3,5,8,13,...な数
  • 定義
    • F0=0,F1=1,Fi=F(i-1) + F(i-2) ただしi>1
  • フィボナッチ数は指数関数的に増加する

用語

  • 漸近的に正:漸近的に正 (asymptotically positive) の関数とは，十分に大きいすべての n に対し て正である関数のことである(p37)
  • 単調増加:m ≤ n ならば f (m) ≤ f (n) であるとき，関数 f (n) は単調増加 (monotonically increasing) であ ると言う(p44)

やってる時のツイート

アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書

アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書