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

3. 대문자 O 표기법

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

O (입력)

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

O(1) ,O(logn), O(n), O(nlogn), O(n2 ) O(2n ) O(n!) 으로 표기

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

O(1) < O(logn) < O(n) < O(nlogn) < O(n2 ) < O(2n ) < O(n!)

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

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

-      n이 1이든 100이든 1000이든 10000이든 실행을 무조건 2회 실행: O(n)

if n> 10:

print(n)

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

varaiable = 1

for num in range(3):

        for index in range(n):

        print (index)

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

variable = 1

for I in range (300):

        for num in range(n):

                   for index in range(n):

                              print(index)

       

       

빅 오 입력값 표기 방법

   예:

-        만약 시간 복잡도 함수가 2n2  + 3n 이라면

     가장 높은 차수는 2n2

      상수는 실제 큰 영향이 없음

        결국 빅 오 표기법으로는 O(n2 ) (서울부터 부산까지 가는 자동차의 예를 상기)

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

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

-      합을 기록할 변수를 만들고 0을 저장

-      n을 1부터 1씩 증가하면서 반복

-      반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함

-      반복이 끝나면 합을 출력

def sum_all(n):

        total = 0

        for num in range(1,n+1):

                   total += num

        return total

sum_all(100)

-      출력:5050

시간복잡도 구하기

-      1부터 n까지 합을 구하는 알고리즘

입력 n에 따라 덧셈을 n번 해야함 ( 반복문!)

시간복잡도 : n 빅오 표기법으로는 O(n)

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

   n(n+1)/2

   def sum_all(n):

           return int(n*(n+1)/2)

 sum_all(100)

-      출력:5050

시간 복잡도 구하기

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

입력 n이 어떻든 간에 곱셈 덧셈 나눗셈 하면됩니다

시간 복잡도:1 , 빅 오 표기법으로는 O(1)

이와 같이 동일한 문제를 푸는 알고리즘은 다양할 수 있습니다. 어느 알고리즘이 보다 좋은지를 객관적으로 비교하기 위해 빅 오 표기법등의 시간복잡도 계산법을 사용합니다

 데이터 구조 6 해쉬 테이블

A.    해쉬구조

Hash Table: 키에 데이터를 저장하는 데이터 구조

-      key를 통해 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라짐

-      파이썬 딕셔너리 타입이 해쉬 테이블의 예 : key를 갖고 바로 데이터를 꺼냄

-      보통 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용

B.     알아둘 용어

-      해쉬: 임의 값을 고정길이로 변환한 것

-      해쉬 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

-      해싱 함수 : key에 대해 산술연산을 이용해 데이터 위치를 찾을 수 있는 함수

 

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

https://bit.ly/2FgOONG