2.2 알고리즘 분석

2.2 알고리즘 분석

 

알고리즘을 실행 시, 필요한 자원 예측

• 메모리
• 통신대역
• 하드웨어
• 계산시간

 

RAM 모델

• 단일 프로세서 + RAM
• 캐시나 가상메모리는 고려하지 않는다.
• 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다.

 

명령어 한 행당 상수시간 소요

• 산술연산(덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림)
• 데이터이동 연산(읽기, 저장하기, 복사하기)
• 제어 연산(조건 분기, 무조건 분기, 함수 호출과 리턴)

 

입력크기는 수행시간에 비례한다.

• 최악의 경우 : 크기가 n인 입력 중 가장 오래걸리는 수행 시간
• 평균적인 경우 : n개의 숫자 무작위

하지만 무엇이 평균적인 입력인지 불확실한 경우, 랜덤화된 알고리즘을 사용한다.

---

연습문제 

 

2.2-1

θ(n³)

 

2.2-2

for s = 1 to A.length
    key = A[s]
    min_value = n + 1 // 범위를 벗어난 최댓값
    for i = s to A.length
        if A[i] < min_value
            min_value = A[i]
            min_value_index = i
    A[s] = min_value
    A[min_value_index] = key

최선 = 최악 모두, θ(n²)

 

마지막 n번째 도달했을 경우, for문을 돌아도 A[n] 와 A[n] 교체하는 로직이고 if문에 걸리지도 않아 사실상 아무런 교체가 이루러지지 않는다. 그래서 탐색 범위를 n-1개까지만 해도 무관하다.

 

2.2-3

2.1-3 나의 풀이

A = <a1, a2, ..., an>

def Search(v)
    for i = 1 to A.length:
        if A[i] == v
            break
            return i
    return NIL

최악의 경우 θ(n), 최선의 경우 θ(1), 평균적인 경우 θ(n)

 

2.2-4

최선의 경우 좋은 알고리즘 수행시간을 갖게 하려면?

• if-break문을 이용해 원하는 해답을 찾았을 경우 불필요한 탐색을 줄인다.
• 탐색범위를 좁혀 탐색시간을 줄인다.