アルゴリズムの効率：実行時間と空間計算量

コンピュータサイエンスの基礎概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

ビッグO記法の導入

入力増加に伴う時間・空間の増え方を測る
例: $O(n)$、$O(n^2)$、$O(log\, n)$
「O」は増加の「次数」を表す。例: O(n) = 線形

時間計算量 — オフィスのたとえ

さまざまなビッグO計算量を示すチャート

$O(1)$ - 定数時間 - 「一目で確認」 - 「定数」
$O(log\,n)$ - ゆるやかに増加 - 「分割の積み重ね」 - 「対数」
$O(n)$ - 線形に増加 - 「文書を読む」 - 「線形」
$O(n\,log\,n)$ - より速く増加 - 「山を並べ替え」 - 「線形対数」
$O(n^2)$ - 二次的に増加 - 「文書を相互比較」 - 「二次」

空間計算量 — オフィスのたとえ

さまざまなビッグO計算量を示すチャート

$O(1)$ - 定数空間 - 「机のスペース」 - 「定数」
$O(log\,n)$ - ゆるやかに増加 - 「最小限のメモ」 - 「対数」
$O(n)$ - 線形に増加 - 「付箋」 - 「線形」
$O(n\,log\,n)$ - より速く増加 - 「一時的な山」 - 「線形対数」
$O(n^2)$ - 二次的に増加 - 「比較グリッド」 - 「二次」

Let's practice!

コンピュータサイエンスの基礎概念

Preparing Video For Download...