복잡도 분석
PS에서 사용하는 복잡도는 시간복잡도와 공간복잡도가 있다. 시간복잡도는 프로그램 수행시간을 분석하는 것이고 반복문에 크게 영향을 받는다.빅오 표기법에서 입력의 크기가 n일 때 주어진 프로그램의 수행시간이 \(5n^4-7n^3+n^2+4\) 의 식을 가진다면.최고차항의 계수와 그보다 낮은 차수의 항을 제외시켜 \(O(n^4)\)와 같이 표기한다.주어진 입력의 크기가 n이라고 하였을 때 아래와 같은 코드들은 각각의 시간 복잡도를 가진다. 주어진 순서대로 위가 가장 빠르다.PS에서 보통 1억을 1초로 잡고 계산한다.예를 들어 n이 1000이라면 6번 이하로는 가능한 알고리즘이다. 공간복잡도는 프로그램의 메모리 사용량을 분석하는 것이다.간단하게 사용한 배열의 크기 * (해당 자료형의 크기) 로 계산한다. 보통 ..
Algorithm
2017. 4. 24. 00:03