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
380
マツコの知らない「数学」の世界
マツコの知らない「数学」の世界
エンジニアとして知っておきたい計算量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.1k
Swift 5.9 と C++ の互換性
hcrane
1
740
Live on iOSDC2023
hcrane
4
1.3k
自販機で1000円を使い切りたいんじゃ!
hcrane
0
140
Vision.framework - 商品画像からのテキスト検出と並列化実装への試み
hcrane
1
780
DevRel/Japan 2023 - 1つの事業部だけで行う DevRel とは
hcrane
0
1k
R2-D2をiOSで動かす
hcrane
2
3.3k
iOSDC2022 - SwiftUI in UIKit で開発する世界
hcrane
6
7.1k
iOSDC2022 - iPadOSDC Japan 2022
hcrane
2
4.1k
Other Decks in Technology
See All in Technology
AIエージェント開発手法と業務導入のプラクティス
ykosaka
2
1.4k
生成AIによるCloud Native基盤構築の可能性と実践的ガードレールの敷設について
nwiizo
7
970
Writing Ruby Scripts with TypeProf
mame
0
170
システムとの会話から生まれる先手のDevOps
kakehashi
PRO
0
290
CodePipelineのアクション統合から学ぶAWS CDKの抽象化技術 / codepipeline-actions-cdk-abstraction
gotok365
5
200
Amazon CloudWatch Application Signals ではじめるバーンレートアラーム / Burn rate alarm with Amazon CloudWatch Application Signals
ymotongpoo
5
530
プロダクト開発におけるAI時代の開発生産性
shnjtk
2
240
AIコーディングの最前線 〜活用のコツと課題〜
pharma_x_tech
3
1.8k
Porting PicoRuby to Another Microcontroller: ESP32
yuuu
4
440
AI AgentOps LT大会(2025/04/16) Algomatic伊藤発表資料
kosukeito
0
140
AIでめっちゃ便利になったけど、結局みんなで学ぶよねっていう話
kakehashi
PRO
0
180
Рекомендации с нуля: как мы в Lamoda превратили главную страницу в ключевую точку входа для персонализированного шоппинга. Данил Комаров, Data Scientist, Lamoda Tech
lamodatech
0
750
Featured
See All Featured
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
23
2.6k
Faster Mobile Websites
deanohume
306
31k
Facilitating Awesome Meetings
lara
54
6.3k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.2k
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
BBQ
matthewcrist
88
9.6k
Music & Morning Musume
bryan
47
6.5k
Documentation Writing (for coders)
carmenintech
69
4.7k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
129
19k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
Six Lessons from altMBA
skipperchong
27
3.7k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
45
7.2k
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