Loading...

O(2^n) - 指数時間

中級

O(2^n) - Exponential Time

部分集合で学ぶO(2^n)。各選択で2倍に爆発する場合の数!

📊 計算量

区分	計算量
最良	O(2^n)
平均	O(2^n)
最悪	O(2^n)
空間	O(n)

🏷️ Tags

計算量指数部分集合

📖 概念紹介

O(2^n)は各要素に2つの選択があり、場合の数が2^n個になります。N+1で時間2倍!

1/11

Loading...

📦部分集合とは？

{A, B, C}の全部分集合を求めましょう。部分集合: 元の集合から一部(または全て/なし)を選んだもの全部で何個？

基礎学習

O(2^n) - 指数時間

定義

O(2^n)は各要素に2つの選択があり、場合の数が2^n個になります。N+1で時間2倍!

主な特性

✓各選択で2倍
✓N+1 → 時間2倍
✓N>30は手に負えない

時間計算量

最良

O(2^n)

平均

O(2^n)

最悪

O(2^n)

空間計算量

O(n)

O(2^n) - 指数時間 | AlgoNote