알고리즘 성능 평가

빅오 표기법 및 알고리즘 실행 시간

알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

 

요구사항에 따라 적절한 알고리즘 설계하기

문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행 시간 요구사항)이다.

시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.

• 𝑁의 범위가 500인 경우: 시간 복잡도가 O(N3) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• 𝑁의 범위가 2,000인 경우: 시간 복잡도가 O(N2) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• 𝑁의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• 𝑁의 범위가 10,000,000인 경우: 시간 복잡도가 O(N) 인 알고리즘을 설계하면 문제를 풀 수 있다.

 

빅오 표기법 예제

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(

): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O(

) : 피보나치 수열

 

출처: https://noahlogs.tistory.com/27 [인생의 로그캣:티스토리]