컴퓨터 科學
分野에서, 주어진 알고리즘의
最善
,
最惡
, 그리고
平均의 境遇
(best, worst, and average cases)는 各
最小
,
最大
,
平均
資源의 使用量을 意味한다. 普通 여기서 考慮하는 資源은 實行時間 (예,
時間 複雜度
:time complexity), 메모리 또는 其他 다른 資源들이다.
最惡의 境遇 알고리즘이 恒常 제時間 안에 끝나는 것을 保障하기 위하여 얼마의 時間 걸리는지 아는 것은 重要하다. 그렇기 때문에 實時間 演算時 最惡의 實行 時間은 重要 考慮事項이 된다.
알고리즘 分析時 平均 性能과 最惡의 境遇 性能이 가장 많이 活用된다. 最善의 境遇 性能은 가장 적게 活用되나 때때로 有用하게 使用된다. 例를 들어 個別 作業의 最善의 境遇 性能을 알고있다면, 이를 通해서 全般的인 最惡의 境遇 分析의 正確度를 向上 시킬수 있다. 豫想 實行 時間을 計算하기 위하여 컴퓨터 科學者들은 確率的 分析 技術들을 使用하며, 特히
期待값
(expected value)을 活用한다.
이 用語들은 다른 文脈에서 活用된다; 例를 들어 最惡/最善의 傳染病 擴散 結果, 電子 回路가 放出하는 最惡의 境遇 溫度 等. 特定 耐性 要素들이 使用되는 곳에서, 裝備들은 最惡의 境遇 內省과 外部 條件 안에서 適切히 作動하도록 디자인 되어야 한다.
알고리즘의 最善의 境遇 性能
[
編輯
]
用語 最善의 境遇 性能(best-case performance)은 電算學에서 最適條件 下에 알고리즘의 動作을 描寫하는데 使用된다. 例를 들어, 리스트(list)의 簡單한 線形 探索 問題에서 最善의 境遇는 願하는 元素가 리스트의 처음에 位置하는 境遇이다.
알고리즘 選擇 및 開發에 있어 最善의 境遇 性能은 거의 活用되지 않으며, 大部分 平均 境遇 複雜度(average-case complexity)와 最惡의 境遇 性能(worst-case performance)의 向上에 關心이 있다. 有限 入力 集合의 하드-코딩(hard-coding) 解決法으로 좋은 最善의 境遇 實行 時間을 가지도록 알고리즘을 修正한다.
[1]
最惡의 境遇 臺 平均 境遇 性能
[
編輯
]
最惡의 境遇(worst-case) 性能 分析과 平均 境遇 性能 分析은 서로 類似性을 가지지만, 두 가지 分析을 위해서 實際로 다른 道具와 接近法이 要求된다.
平均 入力이 무엇인지 定義하는 것은 어렵고, 흔히 平均 入力은 數學的으로 特徵 짓기 어려운 特性을 가진다. 例를 들어 文字列 演算을 위한 알고리즘 亦是 平均 入力을 定義하기 어렵다. 甚至於 特定 “平均 境遇(average case)”의 合理的인 技術이 可能하더라도, 이를 分析하기 위하여 매우 어려운 修飾들을 導出하는 傾向이 있다.
Worst-case 分析은 類似한 問題를 가진다: 一般的으로 正確한 worst-case 시나리오를 決定하는 게 不可能하다. 代身에, 最小 worst case 보다 나쁜 시나리오를 考慮한다. 例를 들어, 알고리즘 分析時, 甚至於 經路를 生成하는 正確한 入力을 決定하는 것이 不可能하더라도 (實在로 그러한 入力이 存在하지 않더라도), 가장 긴 可能한 經路를 찾는 것이 可能하다. (例를 들어 最大 루프 數字를 考慮하기) 이는 安全한 分析을 導出하나(worst case는 決코 過小評價 될 수 없다), 이 經路를 要求하는 入力이 없을 수 있기 때문에, 이는 悲觀的이다.
最惡의 境遇 分析 亦是도 비슷한 問題點을 가진다. 一般的으로 最惡의 境遇 시나리오를 精密하게 定義하는 것은 不可能하다. 代身에, 最惡의 境遇 못지않게 안 좋은 시나리오를 考慮한다. 例를 들어 經路 生成 알고리즘 分析時, 經路를 生成하기 위한 正確한 入力을 決定하는 것이 不可能하더라도 (實際로 그러한 入力이 存在하지 않더라도) 가장 긴 可能한 經路를 찾는 것은 可能하다(예를 들어 最大 루프 回數). 最惡의 境遇 分析은 過小推定(underestimate) 하지 않기 때문에 安定한 分析을 導出한다. 그러나 該當 經路를 要求하는 入力이 없을 수 있기 때문에 매우 悲觀的인 分析이 될 수 있다.
그 代身에 實際 最惡의 境遇와 매우 가깝다고 推定되는 시나리오를 考慮 할 수 있다(그러나 더 나쁜 境遇는 아니다). 이는 樂觀的인 結果를 導出 할 수 있으며, 이 分析은 實際 最惡의 境遇를 過小推定 할 수 있다는 意味를 지닌다.
어떠한 狀況에서는 安定性 保障을 위하여 悲觀的 分析이 必要할 수 있다. 그러나 悲觀的 分析은 자주 매우 悲觀的으로 變할 수 있으며, 樂觀的으로 實際 값과 近接하게 分析하는 것이 훨씬 더 實質的인 接近法이 될 수 있다.
자주 짧은 遂行時間이 걸리나 週期的으로 훨씬 긴 時間을 要求하는 알고리즘들을 分析 할 때, 分割償還分析(amortized analysis)은 連續的인 演算들의 最惡의 境遇 實行 時間을 決定하는데 活用될 수 있다.
이
分割償還
最惡의 境遇(amortized worst-case) 費用은 매우 平均 境遇 費用(average case cost)와 近接함과 同時에 實行 時間의 上向치(upper limit)를 保障한다.
이 最惡의 境遇 分析은 最惡의 境遇 複雜度(worst-case complexity)와 聯關된다.
[2]
實際 結果들
[
編輯
]
最惡의 境遇 性能이 좋지 못한 많은 問題들은 좋은 平均 境遇 性能을 가진다. 解決 하려는 問題들에 對하여 다음은 좋은 接近이다: 特定 事例(instance)들이 平均이기를 바란다. 暗號술(cryptography)에서 다음은 매우 안 좋은 接近이다: 暗號술 問題의 典型的인 事例들이 어려워지길 願한다. 最惡의 境遇가 平均 境遇보다 더 어렵지 않거나, 또는 平均 境遇가 最惡의 境遇 보다 더 쉽지 않은 것을 보이기 위하여, 랜덤 自家-減少性(random self-reducibility)과 같은 이 方法들이 活用될 수 있다.
反面에 最惡의 境遇 分析은
해시 테이블
(hash table)과 같은 알고리즘에 매우 좋지 못한 結果를 얻는다. 그러나 充分한 크기의 잘 쓰인 해쉬 테이블은 統計的으로 絶對 最惡의 境遇가 發生하지 않는다: 平均 演算 回數는 幾何級數的인 減少 曲線을 따르며, 演算의 實行 時間은 統計的으로 制限되기 때문이다.
예제
[
編輯
]
整列 알고리즘
[
編輯
]
| 알고리즘
|
資料 構造
|
時間 複雜度:最善
|
時間 複雜度:平均
|
時間 複雜度:最惡
|
空間 複雜度:最惡
|
| 퀵 整列
|
配列
|
O(
n
log(
n
))
|
O(
n
log(
n
))
|
O(
n
2
)
|
O(1)
|
| 倂合 整列
|
配列
|
O(
n
log(
n
))
|
O(
n
log(
n
))
|
O(
n
log(
n
))
|
O(n)
|
| 힙 整列
|
配列
|
O(
n
log(
n
))
|
O(
n
log(
n
))
|
O(
n
log(
n
))
|
O(1)
|
| 스무스 整列
|
配列
|
O(
n
)
|
O(
n
log(
n
))
|
O(
n
log(
n
))
|
O(1)
|
| 버블 整列
|
配列
|
O(
n
2
)
|
O(
n
2
)
|
O(
n
2
)
|
O(1)
|
| 揷入 整列
|
配列
|
O(
n
)
|
O(
n
2
)
|
O(
n
2
)
|
O(1)
|
| 選擇 整列
|
配列
|
O(
n
2
)
|
O(
n
2
)
|
O(
n
2
)
|
O(1)
|
- 揷入 整列
리스트에
n
個의 모두 다른 元素가 있고 初期 랜덤 順序로 羅列되어 있다고 假定하자. 平均的으로 리스트의
A
1
...
A
j
까지 折半의 元素들은
A
j
+1
보다 작은 값을 가지고 折半은 큰 값을 가진다. 그러므로 알고리즘은 (
j
+ 1)番째 元素와 平均的으로 折半의 이미 整列된 서브-리스트(sub-list)가 比較하며
t
j
=
j
/2 가 된다. 計算 結果 平均 境遇 實行 時間은 最惡의 境遇 實行 時間과 비슷하게 入力 크기에 對한 二次 函數 形態이다.
- 퀵 整列
위와 同一하게 리스트에
n
個의 모두 다른 元素가 있고 初期 랜덤 順序로 羅列되어 있다고 假定하자. 퀵 整列은 平均 境遇 性能이 O(
n
log(
n
))이며 實際로 이는 매우 빠른
整列 알고리즘
에 屬한다. 그러나 最惡의 境遇 入力이 주어졌을 境遇, 性能이 O(
n
2
)까지 低下된다. 또한 “가장 짧은 것 먼저(shortest first)” 方法으로 具現되지 않았다면, 最惡의 境遇 空間 複雜度(worst-case space complexity)는 O(log(
n
))로 性能이 低下된다.
資料 構造
[
編輯
]
| 資料 構造
|
時間 複雜度:平均:인덱싱
|
時間 複雜度:平均:探索
|
時間 複雜度:平均:揷入
|
時間 複雜度:平均:削除
|
時間 複雜度:最惡:인덱싱
|
時間 複雜度:最惡:探索
|
時間 複雜度:最惡:揷入
|
時間 複雜度:最惡:削除
|
空間 複雜度:最惡
|
| 基本 配列
|
O(1)
|
O(
n
)
|
?
|
-?
|
O(1)
|
O(
n
)
|
?
|
?
|
O(
n
)
|
| 動的 配列
|
O(1)
|
O(
n
)
|
O(
n
)
|
?
|
O(1)
|
O(
n
)
|
O(
n
)
|
?
|
O(
n
)
|
| 單一 連結 리스트
|
O(
n
)
|
O(
n
)
|
O(1)
|
O(1)
|
O(
n
)
|
O(
n
)
|
O(1)
|
O(1)
|
O(
n
)
|
| 二重 連結 리스트
|
O(
n
)
|
O(
n
)
|
O(1)
|
O(1)
|
O(
n
)
|
O(
n
)
|
O(1)
|
O(1)
|
O(
n
)
|
| 해시 테이블
|
-
|
O(1)
|
O(1)
|
O(1)
|
?
|
O(
n
)
|
O(
n
)
|
O(
n
)
|
O(
n
)
|
| 李瑱 探索 트리
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
?
|
O(
n
)
|
O(
n
)
|
O(
n
)
|
O(
n
)
|
| B 트리
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
O(
n
)
|
| 레드-블랙 트리
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
O(
n
)
|
| AVL 트리
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
?
|
O((log
n
))
|
O((log
n
))
|
O((log
n
))
|
O(
n
)
|
- 線型 檢索
리스트에
n
個의 元素가 있다고 假定하자. 完全히 最惡의 境遇(absolute worst case)에 線形 檢索은 모든 元素들을 한 番씩 訪問해야 한다. 이 境遇는 찾고자 하는 元素가 리스트의 마지막에 位置하거나 없는 境遇 發生한다. 그러나 찾고자 하는 元素가 리스트에 있고 均等하게 分配되었다고 하면 平均的으로 線型 檢索은
n
/2 元素를 訪問 할 것이다.
같이 보기
[
編輯
]
各州
[
編輯
]
- ↑
Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".
- ↑
“Worst-case complexity”
(PDF)
. 2011年 7月 21日에
原本 文書
(PDF)
에서 保存된 文書
. 2017年 1月 4日에 確認함
.
外部 링크
[
編輯
]