알고리즘의 복잡도 계산

📌 알고리즘의 복잡도 계산

💡 성능분석

1. 주어진 문제를 해결

2. 정확성

3. 문서화
   • 얼마나 주석을 잘 달았는가? / 관련 문서가 얼마나 잘 작성되었는가?

4. 모듈화
   • 함수를 얼마나 체계적으로 잘 나누었는가?

5. 가독성
   • 변수 또는 함수의 이름이 얼마나 의미있게 쓰였는가?

6. 공간 효율성

7. 시간 효율성

• 필수적인 요소 - 1, 2
• 좋은 프로그래밍의 습관 - 3, 4, 5
• 성능과 관련 - 6, 7

💡 성능 분석 VS 성능 측정

1. 성능 분석
   • 시뮬레이션, 복잡도
2. 성능 측정
   • 실제로 실행시켜서 실행 시간을 측정

💡 복잡도의 정의

1. 공간 복잡도 : 프로그램 실행에 사용되는 메모리
2. 시간 복잡도 : 프로그램 실행에 걸리는 시간

💡 시간복잡도

1. 실행에 걸리는 시간(T[p]) = 컴파일 시간 + 실행 시간

   • 컴파일 시간은 고정 and 한번만 필요
   • T[p]는 컴퓨터 사양에 따라 변화한다.

2. 프로그램 단계수 (Program Step)

   • 정의 : 실행시간이 프로그램의 특성과는 무관한 프로그램의 문법적인 혹은 논리적인 단위
   • 프로그램 단계 수의 계산
     • 프로그램에 CNT를 증가시키는 문장을 추가
     • 테이블 방식을 활용