자료구조(5) - 성능분석

 - 프로그램의 성능 평가

              : 프로그램을 실행하는데 필요한 시간, 공간의 추정치를 '분석'하는 방법

              : 실제로 프로그램을 실행하는 데 걸리는 시간을 '측정'하는 방법

              : 모든 프로그램들의 최선, 최악의 상황을 측정하기는 어려운 일 이므로

                성능 분석을 사용

              : 성능분석

                            : 공간적인 효율성

                            : 시간적인 효율성

                            : 위 두가지의 효율성이라는 복잡도를 평가한다. 복잡도와 효율성은 반비례한다.

 

 - 공간 복잡도

              : 프로그램을 실행시켜 완료하는데까지 소요되는 총 저장공간

              : 최악의 경우나 평균의 경우를 고려하여 표현

              : 기억공간이 적게 필요한 최선의 경우보다는 최악의 경우를 고려함

              : 공간 복잡도는 최악이나 평균적으로 얼마나 필요한지를 분석하는 방법

 

              : 공간복잡도 = 고정 공간 + 가변 공간

              : 고정공간

                            : 명령어 저강공간 : 코드 저장을위한 공간

                            : 변수 및 상수의 저장공간

              : 가변 공간

                            : 데이터 구조, 변수의 저장공간

                            : 실행 시간에 필요한 저장공간

 

 - 시간 복잡도

              : 프로그램을 실행시켜 완료하는데까지 걸리는 시간

 

              : 컴파일 시간은 프로그램마다 거의 고정적이며, 실행 시간은 컴퓨터의 성능에 따라 달라질 수 있으므로,

                실제 실행 시간보다는 명령문의 실행 빈도수에 따라 계산

              : 실행 빈도수의 계산은 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행 시간 차이가 거의 없으므로

                하나의 단위 시간을 갖는 기본 명령문으로 취급하여 계산

 

              : 시간 복잡도 = 컴파일 시간 + 실행시간

 

 - 시간복잡도를 구하는 요령

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
• 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
• 컬렉션 정렬을 사용하는 경우 : O(n*log(n))

( 출처 : blog.chulgil.me/algorithm/ )

를 참고하면 좋을 것 같다.