티스토리 뷰

Algorithm

복잡도 분석

박트리 2017. 4. 24. 00:03

PS에서 사용하는 복잡도는 시간복잡도와 공간복잡도가 있다.


시간복잡도는 프로그램 수행시간을 분석하는 것이고 반복문에 크게 영향을 받는다.

빅오 표기법에서 입력의 크기가 n일 때 주어진 프로그램의 수행시간이 \(5n^4-7n^3+n^2+4\) 의 식을 가진다면.

최고차항의 계수와 그보다 낮은 차수의 항을 제외시켜 \(O(n^4)\)와 같이 표기한다.

주어진 입력의 크기가 n이라고 하였을 때 아래와 같은 코드들은 각각의 시간 복잡도를 가진다.



주어진 순서대로 위가 가장 빠르다.

PS에서 보통 1억을 1초로 잡고 계산한다.

예를 들어 n이 1000이라면 6번 이하로는 가능한 알고리즘이다. 


공간복잡도는 프로그램의 메모리 사용량을 분석하는 것이다.

간단하게 사용한 배열의 크기 * (해당 자료형의 크기) 로 계산한다. 

보통 기타 지역변수나 헤더파일, 함수, 등을 생각해서 5~10MB 정도는 여유로 빼고 생각한다.

'Algorithm' 카테고리의 다른 글

문제 해결 전략  (0) 2017.04.24
호프크로프트 카프 알고리즘 (Hopcroft-Karp Algorithm)  (0) 2017.04.03
디닉 알고리즘 (Dinic's Algorithm)  (0) 2017.04.03
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함