[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 44회차 미션

시간복잡도 

-> 실행 시간이라는 관점에서 알고리즘의 효율 측정

-> 문제를 해결하려고 할 때마다 시간복잡도를 분석하는 습관을 들이면 좋은 개발자가 될 수 있다 

-> 이때 가장 중요한 건 연산자의 숫자 혹은 연산과정의 수 

-> 예를 들어 N이라는 인자가 주어졌을 때 1부터 N까지를 더하는 함수를 sumOfN을 정의 

 def sumOfN(N):

   theSum = 0 

   for i  in range(1,N+1):

     theSum += i 

   return theSum 

->함수 sumOfN에서 주요 연산 횟수를 보면 아래와 같습니다 

  def sumOfN(N): 

    theSum  = 0 

   for i  in range ( 1, N+1):

       theSum += i 

   return thesSum

 

함수 sumOfN의 시간 복잡도는 아래와 같이 표시 가능 

    T(n) = 1+ n

    파라미터 n 은 문제의 사이즈를 의미 

    T(n)은 사이즈가 n인 문제를 푸는데 걸리는 시간을 의미 

     여기서는 즉 1+n steps를 의미 

Big- O

   그럼 문제의 사이즈 n에 따라서 알고리즘 수행시간은 어떻게 달라질까 

    문제의 사이즈가 커질수록 최고 차항의 차수가 결과에 가장 많은 영향을 미쳐 

    이처럼 시간 복잡도에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 것을 Big-O 표기법 

    시간복잡도의 표현 법 중 가장 많이 쓰이는 표현 법으로 알고리즘 실행 시간의 상한을 나타낸 표기법 

강의에 대해 정확하게 알고 싶다면 

Big-O 표기법 종류

 

• O(1) - (상수) Constant
  • 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.
  • 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
• O(logN) Logarithmic
  • 데이터양이 많아져도, 시간이 조금씩 늘어난다.
  • 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 된다.
  • 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
  • 만약 입력 자료의 수에 따라 실행 시간이 이 log N 의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.
  • Binary Search
• O(N) Linear
  • 데이터양에 따라 시간이 정비례한다.
  • linear search, for 문을 통한 탐색을 생각하면 되겠다.
• O(N log N) log linear
  • 데이터양이 N배 많이 진다면, 실행 시간은 N배 보다 조금더 많아 진다. (정비례 하지 않는다.)
  • 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고,나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두배로 늘어나면 실행 시간은 2배보다 약간 더 많이 늘어난다.
  • 퀵소트, 머지소트
• O(N^2) Quadratic
  • 데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않음, 사용하면 안된다)
  • 이 유형은 이중루프내에서 입력 자료를 처리 하는 경우에 나타난다. N값이 큰값이 되면 실행 시간은 감당하지 못할 정도로 커지게 된다.
  • 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
  • 2중 for 문을 사용하는 버블소트, 삽입정렬(insertion sort)

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG