알고리즘이란?
문제를 해결하기 위해 프로그램이 수행해야 하는 절차나 방법
🪄좋은 알고리즘을 판단하는 기준들:
1) 정확성 : 얼마나 정확하게 동작하는가?
2) 작업량: 얼마나 적은 연산으로 원하는 결과를 얻어내는가? (→실행시간)
3) 메모리 사용량: 얼마나 적은 메모리를 사용하는가? (→자원절약)
4) 단순성: 다른 사람이 이해하기 쉬운가? (→가독성)
5) 최적성: 더 이상 개선의 여지가 없는가?
알고리즘 성능
위의 예시처럼 하나의 문제를 해결하기 위해서 다양한 알고리즘을 적용할 수 있다. 따라서, 다양한 알고리즘의 성능을 분석하기 위해 시간복잡도를 사용한다.
🕰️시간 복잡도
- 실행되는 명령문의 개수(빈도수)를 계산
- 알고리즘의 작업량을 나타내기 위해서 사용
시간 복잡도를 나타내기 위해서는 점근 표기법으로 사용된다. 주로 사용되는 점근 표기법은 아래와 같이 3가지가 있다.
1. Big-O표기법 O(N) :
빅-오 표기법은 알고리즘 최악의 실행시간을 표기한다
2. Ω 표기법 Ω(N) :
빅-오메가 표기법은 알고리즘 최상의 실행시간을 표기한다
3. Θ 표기법 Θ(N) :
빅-세타 표기법은 알고리즘 평균 실행시간을 표기한다
위의 3가지 중에서 주로 Big-O 표기법이 사용된다!
빅-오(O) 표기법
불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용되는 시간 복잡도 성능 표기법
빅-오 표기법의 규칙
1) 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
2) 계수는 생략
