[Python] 파이썬, 알고리즘 개념 공부하기.- 알고리즘과 빅오표기법

 

 

[Python] 파이썬, 알고리즘 개념 공부하기.- 01

 

---

 

∇ 순서

 

    A. 자료구조

    B. 정렬

    C. 탐색

    D. 탐욕 알고리즘

    E. 정수론

    F. 그래프

    G. 트리

    H. 조합

    I. 동적 계획법.

 

---

∇ 알고리즘이란?

      : 입력값과 원하는 출력값을 매핑시켜주는 절차 [ = 문제 해결을 위한 일련의 단계와 규칙 ]

          - 주어진 문제를 해결하기 위해 어떻게 해야 하는지 명확하게 정의하고,

             이를 수행하는 방법.

           

              -> 모든 인풋에 대해서 정확한 아웃풋이 매핑 되어야 합니다.(정확성)

               -> 해당 알고리즘은 정확한 시간내에(혹은 빠른 시간내에) 아웃풋이 매핑 되어야 합니다(효율성)

                   : 입력값이 주어졌을 때, 출력값이 나오는데 얼마나 시간이 걸리는가??

                       => [ 절대적인 시간을 측정 : 하드웨어 마다 성능의 차이 존재, 따라서 절대적 측정 불가 ]

                       ==>   [  출력값이 나올때까지의 연산의 횟수를 측정 

                                    : 연산횟수는 입력값을 N으로 했을때를 기준.

                                       + 특정 알고리즘은 입력값의 형태에 따라 성능이 변하므로 기준이 필요.[최선/평균/최악]

                                            ++ 최악의 경우가, 제한조건보다 빨라야 한다.!!

 

 

∇ 시간복잡도란?

   : 알고리즘 선택의 기준이 되는 시간 복잡도.

   : 주어진 문제를 해결하기 위한 연산 횟수를 의미합니다. [한마디로 시간이 얼마나 걸리느냐]

         = 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.

         = " 데이터의 크기"와 밀접하게 연관.[크기가 클수록 기하급수적으로 느려진다]

 

       # 시간 복잡도의 유형

             - 빅 오메가( Ω )- 최선의 경우

                    - 알고리즘의 하한선 또는 최소 실행 시간

 

             - 빅 세타( Θ ) - 평균적인 경우

                    - 알고리즘의 평균적인 복잡도/ 상한과 하한이 동일 할 때

 

             - 빅오( O(n) ) -최악의 경우.

                    - 가장 보편적인 사용되는 표기법.

                    - 알고리즘이 최대로 소요할 수 있는 시간.

 

코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋습니다.[데이터 중에 가장 큰 걸로]

# 연산 횟수 계산 방법 : 알고리즘  시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출.