[알고리즘] 1. 알고리즘의 분석: 시간 복잡도

[ 알고리즘? ]

프로그래밍 언어를 사용해 하나의 작업을 수행하는 방법에 대한 서술.

프로그래밍 언어와 독립적일 뿐만 아니라 알고리즘이 구현된 프로그램을 실행하는 기계와도 독립된 추상적인 실체.

 

---

알고리즘의 분석 *실행시간의 분석

알고리즘의 자원(resource: 실행시간, 메모리, 저장장치, 통신 등) 사용량을 분석.

 

시간 복잡도

• 실행 시간은 실행 환경에 따라 달라짐 ex) 하드웨어, 운영체제, 언어, 컴파일러 등
• 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트
• 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
• 데이터의 크기가 같더라도 실제 데이터에 따라 다름 ex) 최악의 경우 시간복잡도( worst-case analysis), 평균 시간복잡도(average-case analysis)

점근적(Asymptotic) 분석

점근적 표기법?

• 데이터의 개수 n→∞ 일 때 수행시간이 증가하는 growth rate로 시간 복잡도를 표현
• 알고리즘에 포한된 연산들의 실행 횟수를 표기하는 하나의 기법
• 최고차항의 차수만으로 표시
• Θ-표기, Ο-표기 등을 사용.
• 다른 표기법에 비해 간단하고 알고리즘의 실행환경에 비의존적 -> 가장 광범위하게 사용

-> 데이터의 개수가 무한으로 늘어날 때 수행시간이 증가하는 수치로 시간 복잡도를 표현하는 기법.

-> 가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려함

 

ex) 최소 시간 : 시간 복잡도

      최소 환승 : 공간 복잡도

 

' Ο- ' 표기법

upper bound를 표시

 

' Ω- ' 표기

lower bound를 표시

 

' Θ- '표기

upper bound와 lower bound를 동시에 표현

 

 

 

-- chap01_time_complexity.key 15~19p 이해 필요

 

---

예시

 

상수 시간복잡도

// 입력으로 n개의 데이터가 저장된 배열 data가 주어지고,
// 그 중 n/2번째 데이터를 반환한다.

func sample(data: [Int], n: Int) -> Int {
    var k = n/2
    return data[k]
}

-> n에 관계 없이 상수 시간이 소요된다. 이 경우 알고리즘의 시간 복잡도는 O(1)이다.

 

선형 시간복잡도

// 입력으로 n개의 데이터가 저장된 배열 data가 주어지고,
// 그 합을 구하여 반환한다.
func sample2(data: [Int], n: Int) -> Int {
    var sum = 0
    for i in 1...n{
        sum = sum + data[i]
    }
    return sum
}

이 알고리즘에서 가장 많이 실행되는 문장의 실행 횟수는 항상 n번이다. 가장 자주 실행되는 문장의 실행 횟수가 n번이라면, 모든 문장의 실행횟수의 합은 n에 선형적으로 비례하며, 모든 연산들의 실행 횟수의 합도 n에 선형적으로 비례한다.

-> 선형 시간복잡도를 가진다고 말하고 O(n)이라고 표기한다.

 

- 순차 탐색

// 배열 data에 정수 target이 있는지 검색한다.
func sample3 (data: [Int], target: Int) -> Int {
    var n = 0
    for i in 0...data.count-1 {
        if data[i] == target {
            n = i
            return n
        }
    }
    return 1
}

데이터의 개수가 n개라고 할 때( == data.count) 최악의 경우(맨 마지막 인덱스의 값이 target일 때) 해당 for문은 n번 돌아야 한다.

-> 최악의 경우 시간복잡도는 O(n)이다.

 

// 배열 data에 중복된 원소가 있는지 검사하는 함수이다
func sample4 (data: [Int]) -> Bool {
    for i in 0...data.count-1 {
        for j in i+1...data.count-1{
            if data[i] == data[j] && j <= data.count-1{
                return true
            }
            
        }
    }
    return false
}

최악의 경우 배열에 저장된 모든 원소 쌍을 비교하므로 비교 연산의 횟수는 n(n-1)/2이다.

-> 최악의 경우 시간복잡도는 O(n^2)이다.