SW 문제 해결; 성능 계산

알고리즘 성능

---

무엇이 좋은 알고리즘인가

• 정확성 : 얼마나 정확하게 동작하는가
• 작업량 : 얼마나 적은 연산으로 원하는 결과를 해결하는가
• 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
• 단순성 : 얼마나 단순한가
• 최적성 : 더 이상 개선할 여지가 없는가(처음부터 고려할 사항은 아님)시간 복잡도, 공간 복잡도

 

시간 복잡도, 공간 복잡도

• 시간 복잡도
  • 최선의 경우
    • 빅 오메가 표기법 사용
    • 최선일 경우 최소 이 시간이 걸림
  • 최악의 경우
    • 빅 오 표기법 사용
    • 최악이어도 이 시간보다 덜 걸림.
    • 우리가 말하는 일반적인 시간 복잡도는 빅 오 표기법
  • 평균적인 경우
    • 빅 세타
• 공간 복잡도

 

알고리즘 성능

• java 연산 기준
  • 작업략 기준
    • 1억번의 연산은 1초라고 대충 기준
    • 1초를 넘어서는 알고리즘은 피하기
  • 재귀 호출 횟수
    • 재귀 호출이 몇 번인지를 파악해서 고려

 

빅-오(O) 표기법

• 가장 큰 영향력을 주는 최고 차항만 표시
  • 계수, 상수는 생략하는 것이 일반적

 

다양한 시간 복잡도의 비교

• 기억해둘 것
  • 2^n
    • n=10, 1000
    • n=20, 100만
    • n=30, 10억
  • n!
    • n=10, 360만
    • n=11, 4000만
    • n=12, 초과 위험도 높음