패스트캠퍼스 챌린지 9일차

<학습일기>

Ch 08. 알고리즘 복잡도 표현 기법 - 시간복잡도-2

 

3. 대문자 O표기법

- 빅오 표기법, Big-O 표기법이라고도 부름

- O(입력)

 - 입력 n에 따라 결정되는 시간 복잡도 함수

 - O(1), O(𝑙𝑜𝑔𝑛), O(n), O(n𝑙𝑜𝑔𝑛), O(𝑛제곱), O(2의𝑛제곱), O(n!)등으로 표기함 

 - 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음

  - O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(n제곱) < O(2의n제곱) < O(n!)

   - 참고: log n 의 베이스는 2, (일반적으로는 10)

- 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 된다.

 - **표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다.

 - n이 1이든 100이든, 100이든, 10000이든 실행을

  - 무조건 2회(상수회) 실행한다 : O(1)

   ex) if n > 10 :

          print(n)

  - n에 따라 n번, n+10번 또는 3n+10번등 실행한다 : O(n)

   ex) 

    variable = 1 --> 상수번을 곱하거나, 상수번을 더해도 n이라는 숫자가 무한정이라고 생각하면 큰 의미가 없어진다.

    for index in range(n):                       따라서 O(n)이라고 표기해도 된다.

        print(index)

  - n에 따라 𝑛2번, 𝑛2 + 1000 번, 100𝑛2 - 100, 또는 300𝑛2 + 1번등 실행한다: O(𝑛2)

    variable = 1

    for i in range(300):

        for num in range(n):

            for index in range(n):

                print(index)

 - 빅 오 입력값 표기 방법

  - 예:

   - 만약 시간 복잡도 함수가 2n제곱 + 3n이라면 : 상수곱은 무시할정도가 됨

    - 가장 높은 차수는 2n제곱

    - 상수는 실제 큰 영향이 없음

    - 결국 빅 오 표기법으로는 O(n제곱)

     --> 서울에서 부산까지 가는 자동차의 예를 생각해보면 제곱이 가장 큰 영향을 미침

 

4. 실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기

- 1부터n까지의 합을 구하는 알고리즘 작성해보기

 

 알고리즘1: 1부터 N까지의 합을 구하는 알고리즘1

  def sum_all(n):
      total = 0
      for num in range(1, n+1):
          total +=num
      return total

 알고리즘2: 1부터 N까지의 합을 구하는 알고리즘2

  --> n*(n+1)/2

  def sum_all(n):
      return int(n * (n + 1) / 2)

 

--> 1과 2의 값이 같음. 시간 복잡도를 구해야한다.

 

- 시간 복잡도 구하기

 알고리즘1: 반복문이 n번 수행함. : O(n)

 알고리즘2: n의 수의 상관없이 1번 수행함 : O(1)

 --> 어느 알고리즘 성능이 좋을까? : O(1)이 n의 값이 무한정 늘어나더라도 일정하기 때문에 O(1)이 성능이 좋다.

정리

이와 같이, 동일한 문제를 푸는 알고리즘은 다양할 수 있다.

따라서 어느 알고리즘이 보다 좋은지를 객관적으로 비교하기 위해, 빅 오 표기법등의 시간복잡도 계산법을 사용한다.

 

<학습일기>그 동안 알고리즘을 풀 때, 반복을 하는게 나은지, 분기분을 나누어도 되는지 이런 고민을 했었는데 그 고민의 답을 찾은 것 같아서 다행이다.

---

<수강인증>

강의 수강

필기

 

---

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.*

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

#패스트캠퍼스 #패캠챌린지 #직장인인강 #직장인자기계발 #패스트캠퍼스후기

#알고리즘기술면접완전정복올인원패키지Online