알고리즘 2강 :: 대표적인 알고리즘 3가지, 점근 성능

알고리즘 2강을 보며 배운내용

 

 

알고리즘의 정의

입출력, 명확성, 유한성, 유효성을 만족하고 효율적이어야 한다

 

 

순차탐색

처음부터 순서대로 찾는 방법

 

 

이진 탐색

반으로 나눠서 탐색

순서대로 되어있을 때 사용하면 좋다

랜덤이면 사용할 수 없다

 

 

대표적인 알고리즘 설계 기법 3가지

• 분할정복(divide and conquer)
• 동적 프로그래밍(dynamic programming)
• 욕심쟁이(greedy)

 

 

알고리즘 분석

정확성, 효율성

 

효율성 분석

메모리 양 => 공간 복잡도(space complexity)

수행 시간 => 시간 복잡도(time complexity)

메모리 적게 쓰고, 수행 시간 짧은게 좋은 알고리즘

보통 시간 복잡도만 따진다(메모리는 구하기 쉬워서)

 

시간 복잡도

알고리즘 단위 연산의 수행 횟수의 더해서 계산

• 입력 크기 n에 대한 함수 f(n)으로 표현
• 최악의 수행 시간을 시간 복잡도로 사용한다

 

 

점근성능

입력 크기 n이 무한대로 커졌을때 결정되는 성능

최고차항만 가져와서 표현 => 정확한 값 아니다

 

• Big-oh 표기법
• Big-omega 표기법
• Big-theta 표기법

루프의 반복 횟수 조사해서 시간복잡도로 사용

 

기본 점화식과 폐쇠형