Upgrade to Pro — share decks privately, control downloads, hide ads and more …

マツコの知らない「数学」の世界

h.crane
December 26, 2019

 マツコの知らない「数学」の世界

マツコの知らない「数学」の世界

エンジニアとして知っておきたい計算量O(n)のお話

h.crane

December 26, 2019
Tweet

More Decks by h.crane

Other Decks in Technology

Transcript

  1. 1 ≦ M ≦ 50 1 ≦ M ≦ 10

    * 5 1 ≦ M ≦ 10 * 5 ≦ 10 * 10 Mの範囲をNに合わせて拡張する 上記のことから 1 ≦ M ≦ 10²
  2. O(NM²) ≦ O(MN log N) ≦ O(MN²) O(MN²) ≦ O(10²

    * (10⁵)²) ≦ O(10² * 10¹⁰) ≦ O(10¹²) O(MN log N) ≦ O(10² * 10⁵ * log10⁵) ≦ O(10⁷ * 10⁵) ≦ O(10¹²) O(NM²) ≦ O(10⁵ * (10²)²) ≦ O(10⁵ * 10⁴) ≦ O(10⁹) N = 10⁵, M = 10²
  3. O(NM²) ≦ O(MN log N) ≦ O(MN²) O(10⁹) ≦ O(10¹²)

    ≦ O(10¹²) 10⁹ ≦ 10¹² ≦ 10¹²
  4. fin