알고리즘 - 알고리즘이란

 

알고리즘이란

주어진 문제를 해결하기 위한 일련의 처리과정을 단계적으로 나열한 것

입출력 / 명확성 / 유한성 / 유효성

설계 → 기술 → 정확성 분석 → 효율성 분석

 

알고리즘의 기본 자료구조

선형 자료구조 : 배열 / 연결 리스트 / 스택 / 큐

비선형 자료구조 : 트리 / 그래프

 

알고리즘의 대표적인 설계기법

- 분할 정복 방법

- 동적 프로그래밍 방법 

- 욕심쟁이 방법

 

알고리즘의 분석

정확성 / 효율성 분석 (공간 복잡도 & 시간복잡도)

 

- 시간 복잡도

알고리즘을 실행시켜 완료까지 걸리는 시간으로

알고리즘에서 수행되는 단위 연산의 총 횟수로 계산된다

입력 크기의 함수로 표현하며 최악의 수행 시간을 사용한다

 

점근 성능

입력 크기가 충분히 커질 때의 알고리즘 성능

다항식의 수행 시간에 대해서 계수 없이 최고 차항 만을 표시

- 점근적 상한 일 때 f(n) = O(g(n))

- 점근적 하한 일 때 f(n) = Ω(g(n))

- 점근적 상하한 일때 f(n) = 𝛩(g(n))

 

Big O 표기법

알고리즘의 정확한 수행시간이 아닌 입력 크기가 증가함에 따라 수행시간이 어떤 추세로 증가하는 지를 표시

입력크기가 커질 수록 수행시간의 차이가 확연하게 나타나므로 효율적인 알고리즘이 중요하다

O(1) <  O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)

 

 

순환 알고리즘의 성능

분할 정복 방법을 적용한 알고리즘은 기본적으로 순환 알고리즘의 형태를 가짐 (점화식으로 표현)

퀵 정렬(최악) : T(n) = T(n - 1) + 𝛩(n) , T(1) = 𝛩(1) → 𝛩(n²)

이진 탐색 : T(n) = T(n / 2) + 𝛩(1) , T(1) = 𝛩(1) → 𝛩(log n)

퀵 정렬(최선), 합병 정렬 : T(n) = 2T(n / 2) + 𝛩(n), T(1) = 𝛩(1) → 𝛩(n log n)