[PS-Basics] 1. 복잡도

• 복잡도 : 알고리즘의 성능을 나타내는 척도

 

• 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석

 

 

파이썬은 1초에 약 2000만 번 연산하는 것을 기준으로 생각함!!

 

<시간 복잡도 도출 기준>

1. 상수는 시간 복잡도 계산에서 제외한다.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

  

 

 

• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

• 복잡도가 낮을수록 좋은 알고리즘임

 

• 빅오 표기법 (big-O notation) : 최악일 때의 연산횟수를 나타낸 표기법

• 가장 빠르게 증가하는 항만을 나타내는 표기법 (함수의 상한만을 표기)

• 연산 횟수 = 3N^3+5N^2+1000000 -> O(N^3) : 최고차항만 남기고, 계수 날리기

 

• 주어진 데이터의 '개수'에 따른 '총 연산횟수'

 

• O(1) : 상수 시간 (BETTER)

• O(logN) : 로그 시간

• O(N) : 선형 시간

• O(NlogN) : 로그 선형 시간

• O(N^2) : 이차 시간

• O(N^3) : 삼사 시간

• O(2^n) : 지수 시간 (WORSE)

 

• 시간제한이 1초인 문제 : 

• N의 범위가 500 : O(N^3)

• N의 범위가 2,000 : O(N^2)

• N의 범위가 100,000 : O(NlogN)

• N의 범위가 10,000,000 : O(N)

 

• 알고리즘 문제 해결 과정

• 1. 지문 읽기 및 컴퓨터적 사고

• 2. 요구사항(복잡도) 분석

• 3. 문제 해결을 위한 아이디어 찾기

• 4. 소스코드 설계 및 코딩