[알고리즘] 알고리즘 효율성표현(ALGORITHM)(4)

안녕하세요, 오늘은 프로그래머였던 붐붐몬의 지식 나눔 자리입니다.
알고리즘 관련해서 
1. 알고리즘 어원 
2. 최초의 알고리즘 
3. 알고리즘 표현방법 
4. 효율성 표현
4가지로 우선 정리할 예정이에요. 

1. 알고리즘의 효율성 표현 이유 
      (1)  알고리즘 설계 후 주어진 문제를 정확히 해결했는지 확인 
          - 수학적 기법들로 증명 가능해야 함 
          :유효한 입력에 대해 유한 시간 내에 정확한 답을 계산하는 경우 정확하다고 함 

     (2)  설계한 알고리즘이 컴퓨터 자원을 얼마나 필요로 하는지 분석 필요 
          - 자원 
              ①  알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기- 공간 복잡도(Space Complexity) 
              ②  알고리즘 수행 시간 - 시간 복잡도(Time Complexity)  
              ③  입출력 장치의 종류와 수 
2. 복잡도 종류 
      (1) 시간 복잡도(Time Complexity)  
          - “ 입력 크기에 따라 단위 연산이 몇 번 수행되는가?”  
               = 알고리즘의 수행 시간 

      (2) 공간 복잡도(Space Complexity)  
          - “입력 크기에 따라 작업공간이 얼마나 필요한가?”  
               =알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기 


→일반적으로 “시간복잡도”를 사용 
      이유 
      : 알고리즘이 수행되는 동안에 사용되는 메모리 크기가 극히 제한적일 때 
      (ex)임베디드 시스템)만 중요하지만 하드웨어의 발전으로 신경 안 써도 됨 
      즉, 시간 복잡도가 공간 복잡도와 같다고 생각해도 무관 

3. 시간의 복잡도
      (1) 최악 경우 분석(worst case analysis) - Big-Oh 
          -  어떤 입력이 주어지더라도 얼마 이상을 넘지 않는다’ 
          단위연산이 수행되는 횟수가 최대인 경우 
          최악 경우 시간(Worst-Case-Time) 
          : 입력 크기가 n인 모든 입력에 대해 알고리즘을 실행하는데 걸리는 최대 시간 

      (2) 평균 경우 분석(average case analysis) 
          -  입력이 무작위로 주어진다고 가정 
          모든 입력에 대하여 단위연산이 수행되는 기대치(평균)을 선택 
          평균 경우 시간(Average-Case-Time) 
          :입력 크기가 n인 모든 입력에 대해 알고리즘을 실행하는 데 걸리는 평균 시간  

      (3) 최선 경우 분석(best case analysis) – BIG-omega 
          -  단위연산이 수행되는 횟수가 최소인 경우 선택 
          최적의 알고리즘 고안하는데 참고자료로 사용 
          최선 경우 시간(Best-Case-Time) 
          :입력 크기가 n인 모든 입력에 대해 알고리즘을 실행하는 데 걸리는 최소 시간 

4. 시간의 복잡도 예시
      If ) 철수는 매일 지하철을 타고 등교 지하철역까지 6분
      지하철 타고 학교 근처 역까지 20분
      역에서 강의실까지 10분 소요

      “늦어도 40분이면 간다”
      = 최악의 경우 제시
      이유 : 대부분의 알고리즘이 입력에 따라서 그 수행시간이 다름
      프로그래머는 안전하거나 안정된 프로그램을 구현해야 하므로 최악의 경우를 가정하고 알고리즘을 설계 해야 됨

 

[출처]http://blog.naver.com/childcat?Redirect=Log&logNo=140210204282
http://blog.naver.com/backjookiki
http://carstart.tistory.com/122
http://destiny738.tistory.com/162