Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
マツコの知らない「数学」の世界
Search
h.crane
December 26, 2019
Technology
0
390
マツコの知らない「数学」の世界
マツコの知らない「数学」の世界
エンジニアとして知っておきたい計算量O(n)のお話
h.crane
December 26, 2019
Tweet
Share
More Decks by h.crane
See All by h.crane
Getting started with controlling LEGO using Swift
hcrane
1
1.2k
Swift 5.9 と C++ の互換性
hcrane
1
850
Live on iOSDC2023
hcrane
4
1.4k
自販機で1000円を使い切りたいんじゃ!
hcrane
0
170
Vision.framework - 商品画像からのテキスト検出と並列化実装への試み
hcrane
1
820
DevRel/Japan 2023 - 1つの事業部だけで行う DevRel とは
hcrane
0
1.1k
R2-D2をiOSで動かす
hcrane
2
4.1k
iOSDC2022 - SwiftUI in UIKit で開発する世界
hcrane
6
7.5k
iOSDC2022 - iPadOSDC Japan 2022
hcrane
2
4.4k
Other Decks in Technology
See All in Technology
7月のガバクラ利用料が高かったので調べてみた
techniczna
3
820
Oracle Cloud Infrastructure:2025年8月度サービス・アップデート
oracle4engineer
PRO
0
170
生成AI時代に必要な価値ある意思決定を育てる「開発プロセス定義」を用いた中期戦略
kakehashi
PRO
1
250
データアナリストからアナリティクスエンジニアになった話
hiyokko_data
2
330
Language Update: Java
skrb
2
230
制約理論(ToC)入門
recruitengineers
PRO
9
3.7k
Nstockの一人目エンジニアが 3年間かけて向き合ってきた セキュリティのこととこれから〜あれから半年〜
yo41sawada
0
180
Kubernetes における cgroup v2 でのOut-Of-Memory 問題の解決
pfn
PRO
0
450
BPaaSにおける人と協働する前提のAIエージェント-AWS登壇資料
kentarofujii
0
110
Function Body Macros で、SwiftUI の View に Accessibility Identifier を自動付与する/Function Body Macros: Autogenerate accessibility identifiers for SwiftUI Views
miichan
2
150
ヒューリスティック評価を用いたゲームQA実践事例
gree_tech
PRO
0
430
AWSで推進するデータマネジメント
kawanago
0
880
Featured
See All Featured
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
252
21k
BBQ
matthewcrist
89
9.8k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
358
30k
The Cult of Friendly URLs
andyhume
79
6.6k
A designer walks into a library…
pauljervisheath
207
24k
Fireside Chat
paigeccino
39
3.6k
Building Adaptive Systems
keathley
43
2.7k
Optimizing for Happiness
mojombo
379
70k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Testing 201, or: Great Expectations
jmmastey
45
7.6k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Visualization
eitanlees
147
16k
Transcript
マツコの知らない「数学」の世界 〜 エンジニアとして知っておきたい計算量O(n)のお話 〜 Hiromu Tsuruta
こんな記事がバズってました
動的計画法によるDVDのディスク分割の改善
何でバズってるの?
アルゴリズムを使って実際に業務改善をしている!
・家族の「写真や動画」をDVDにして注文できる機能がある ・「写真や動画」は1枚に収まらないので複数のディスクに分割する ⇨ 「月ごとに分けて各ディスクに入れていく」というアルゴリズム 【前提】
1月の思い出 データベース 2月の思い出 3月の思い出 12月の思い出 ・・・・・ 12枚 【現状】
ディスクの枚数をもっと減らせないのか ⇨ ユーザーから問い合わせが寄せられていた 【課題】
どうやって減らす?
月ごとではなく最適化して入れる!
1月の思い出 データベース 2月の思い出 3月の思い出 12月の思い出 ・・・・・ 12枚よりは少ない 【解決例】
最適化する = データを分割する
ディスクの枚数課題を解決!
ではありません
ただ、分割すれば良いと言うものではない!
なんで?
データ分割の計算量を意識する必要がある
None
ユーザー サーバー ① アルバムの注文 ④ 注文枚数を表示 サーバー/データ ② 枚数の計算を実行 ③
計算結果を返す 〜 注文フロー 〜
計算が遅いとユーザーの画面反映も遅れる
UXの低下・機会損失
ユーザー サーバー ① アルバムの注文 ④ 注文枚数を表示 サーバー/データ ② 枚数の計算を実行 ③
計算結果を返す 〜 注文フロー 〜 この部分をなんとかしたい!
計算量を抑えました
O(MN²) から O(MN log N) まで減らし 最終的に O(NM²) までになりました (1
≦ N ≦ 10⁵, 1 ≦ M ≦ 50)
ん?
O とは?
ランダウの記号 ギリシア文字の O(オミクロン)を用いて表される 大文字をビッグオー、小文字をスモールオーと呼んだりもする 数学においてはオーダーという呼び方をする 計算量を大雑把に評価する(見積もる)際に使用する example O(n) :オーダーのエヌ O(log
n) :オーダーのログエヌ
具体例を見てみよう!
Example.1 「世界のナベアツ」
None
ナベアツは線形探索しているだけ!
線形探索とは?
・検索アルゴリズムの1つ ・リストや配列に入ったデータの検索を行う ・先頭から順に比較を行い、見つかれば終了する
「世界のナベアツ」パターン - 3の倍数 or 3が付くなら true - それ以外は false を必ず1回ずつ確認を行っている
and 40までしか探索しない
「世界のナベアツ」= O(40)
「世界のナベアツ」が 100 まで探索する場合は?
「世界のナベアツ」= O(100)
「世界のナベアツ」が n まで探索する場合は?
「世界のナベアツ」= O(n)
話を戻すと、、 結局、計算量は減ってるの? (ここから普通に数学なのでつまらなかったらすいません)
O(MN²) ⇨ O(MN log N) ⇨ O(NM²) 先の話では、、 計算量を以下の順番で減らした O(NM²)
≦ O(MN log N) ≦ O(MN²) (1 ≦ N ≦ 10⁵, 1 ≦ M ≦ 50)
全然わからん、、から 具体的な数字に落とし込んでみよう!
取りうる最大値を代入する
1 ≦ N ≦ 10⁵ 1 ≦ M ≦ 50
1 ≦ M ≦ 50 1 ≦ M ≦ 10
* 5 1 ≦ M ≦ 10 * 5 ≦ 10 * 10 Mの範囲をNに合わせて拡張する 上記のことから 1 ≦ M ≦ 10²
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²
O(NM²) ≦ O(MN log N) ≦ O(MN²) O(10⁹) ≦ O(10¹²)
≦ O(10¹²) 10⁹ ≦ 10¹² ≦ 10¹²
確かに計算上は計算量が小さくなっている!
どうやって小さくしているの? というのはバズっていた記事にある アルゴリズムを読んでください (この資料はあくまでもO(オーダー)について説明に焦点を当てています)
fin