| English | 의미 |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | 알고리즘 효율성 |
| slow/sləʊ/ | 느린 |
| steps/steps/ | 단계 |
| reasonable/ˈriːzənəbl/ | 합리적인 |
| unreasonable/ʌnˈriːzənəbl/ | 부당함 |
| heuristic/hjuːˈrɪstɪk/ | 히ュー리스틱 |
정확함만으로 충분하지 않을 수도 있음
- 두 알고리즘이 모두 정확할 수 있으나, 그중 하나는 사용하기 훨씬 더 낳을 수 있습니다.
- 알고리즘 효율성(algorithmic efficiency) 은 주로 시간과 메모리와 같은 자원을 소모하는 정도에 따라 알고리즘을 비교합니다.
- 정확하지만 느린 알고리즘은 큰 입력 데이터에서는 쓸모가 없을 수 있습니다.
- 따라서 확장성(scaling) 을 어떻게 하는지 비교할 수 있는 방법이 필요합니다.
알고리즘 효율성은 다음에 따라 알고리즘을 비교합니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
효율성은 입력이 커질 때 시간과 메모리와 관련됩니다.
n이 커질수록 단계 수 세기
- 입력 크기 $n$가 커질 때 알고리즘이 소모하는 단계(steps) 의 개수를 추정하십시오.
- 선형 탐색(linear search)은 약 $n$개의 단계를 요구하고, 이진 탐색(binary search)은 약 $\log_2 n$개, 모든 쌍을 비교하는算法은 약 $n^2$개를 요합니다.
- $n$가 커지면 이러한 차이점은 극적으로 커집니다.
- 성장의 모양이 스톱워치를 훨씬 더 중요하게 만듭니다.
n에 따른 실행 시간의 성장 양상
슬라이드 n을 비교하고 곡선을 확인하세요: log n은 거의 평평하게 유지되고, n은 일정하게 상승하며, n²는 폭발적으로 증가합니다. 이것이 우리가 스톱워치를 사용하지 않고 알고리즘을 확장성에 따라 비교하는 이유입니다.
각 알고리즘을 입력 크기 n에 대한 대략적인 단계 수와 매칭하세요.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
이 성장 속도가 어떤 알고리즘이 확장 가능한지 결정합니다.
n이 커질 때 어떤 성장이 합리적이지 않다고 간주합니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
지수 성장은 매우 빠르게 너무 느려집니다.
정확한 답을 구하는 것이 너무 느릴 경우, ______는 충분히 좋은 해를 빠르게 찾습니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
히어리스틱은 완벽한 대가를 속도로教务합니다.
합리적인 vs 비합리적인
- 합리적인 실행 시간과 비합리적인 실행 시간을 구분합니다.
- 대략적으로 $n$ 또는 $n^2$와 같은 성장 속도는 합리적이지만, 추가 요소마다 처리 단계를 두 배로 늘리는 것($2^n$)은 비합리적입니다.
- 정확한 답을 구하는 데 시간이 너무 많이 걸릴 경우 히어리스틱을 사용하세요. 이는 빠르게 도출된 충분히 좋은 해결책입니다.
- 완벽하지는 않으나, 시간 내에 완벽한 해법을 찾을 수 없는 상황에서 유용합니다.
1,000,000개의 정렬된 항목에 대한 이진 탐색은 최대 약 몇 단계가 필요합니까? (2^20 ≈ 백만)
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
2^20이 백만稍过因此，约20次减半即可满足需求。
올바른 알고리즘이라도 큰 입력에는 사용하기에 너무 느릴 수 있습니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
또한 합리적인 시간 내에 완료되어야 합니다.
사용하기에도 너무 느림
- 이것이 바로 일부 정확한 알고리즘이 실제large 입력에 대해 실행하기에 너무 느리게 작동하는 이유입니다.
- 정확함만으로는 충분하지 않습니다. 알고리즘도 합리적인 시간 내에 완료되어야 합니다.
백만 개의 항목. 정렬된 1,000,000개 항목에 대한 선형 검색은 최대 1,000,000개의 단계가 소요될 수 있습니다. 이진 검색은 최대 약 20단계면 충분하며, 이는 $2^{20}$가 백만稍过이기 때문입니다. 작은 목록에서는 차이가 거의 없지만, 백만 개 항목에서는 이진 검색만이 합리적인 선택지입니다.
알고리즘 효율성은 입력 크기 $n$가 커짐에 따라 리소스를 기준으로 알고리즘을 비교합니다: 선형 $n$, 이진 $\log_2 n$, 전쌍 $n^2$. $n$나 $n^2$와 같은 증가는 합리적인 것으로 간주되지만, $2^n$는 비합리적입니다(이 경우 히ュー리스틱을 사용해야 합니다). 큰 입력에서 너무 느린 올바른 알고리즘도 충분하지 않습니다.