알고리즘 복잡도 (시간 복잡도)
이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을
오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
● 잔재미코딩 유투브 오픈
[구독해보기]
2. 알고리즘 복잡도 표현 방법¶
알고리즘 시간 복잡도의 주요 요소¶
반복문이 지배합니다.
생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?
- 예:
- 자동차로 서울에서 부산가기
- 자동차 문열기
- 자동차 문닫기
- 자동차 운전석 등받이 조정하기
- 자동차 시동걸기
- 자동차로 서울에서 부산가기
- 자동차 시동끄기
- 자동차 문열기
- 자동차 문닫기
- 자동차로 서울에서 부산가기
마찬가지로, 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문¶
- 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
알고리즘 성능 표기법¶
Big O (빅-오) 표기법: O(N)
- 알고리즘 최악의 실행 시간을 표기
- 가장 많이/일반적으로 사용함
- 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
Ω (오메가) 표기법: Ω(N)
- 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
Θ (세타) 표기법: Θ(N)
- 오메가 표기법은 알고리즘 평균 실행 시간을 표기
시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨
3. 대문자 O 표기법¶
빅 오 표기법, Big-O 표기법 이라고도 부름
O(입력)
- 입력 n 에 따라 결정되는 시간 복잡도 함수
- O(1), O($log n$), O(n), O(n$log n$), O($n^2$), O($2^n$), O(n!)등으로 표기함
- 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
- O(1) < O($log n$) < O(n) < O(n$log n$) < O($n^2$) < O($2^n$) < O(n!)
단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
- 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.
- n이 1이든 100이든, 1000이든, 10000이든 실행을
- 무조건 2회(상수회) 실행한다: O(1)
- n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)
- n에 따라, $n^2$번, $n^2$ + 1000 번, 또는 100$n^2$ - 100 번등 실행한다: O($n^2$)
- 빅 오 입력값 표기 방법
- 예:
- 만약 시간 복잡도 함수가 2$n^2$ + 3n 이라면
- 가장 높은 차수는 2$n^2$
- 상수는 실제 큰 영향이 없음
- 결국 빅 오 표기법으로는 O($n^2$) (서울부터 부산까지 가는 자동차의 예를 상기)
- 만약 시간 복잡도 함수가 2$n^2$ + 3n 이라면
- 예:
4. 실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기¶
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다
연습1: 1부터 n까지의 합을 구하는 알고리즘 작성해보기
알고리즘1: 1부터 n까지의 합을 구하는 알고리즘1¶
- 합을 기록할 변수를 만들고 0을 저장
- n을 1부터 1씩 증가하면서 반복
- 반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함
- 반복이 끝나면 합을 출력
In [16]:
def sum_all(n):
total = 0
for num in range(1, n + 1):
total += num
return total
In [17]:
sum_all(100)
Out[17]:
시간 복잡도 구하기¶
- 1부터 n까지의 합을 구하는 알고리즘1
- 입력 n에 따라 덧셈을 n 번 해야 함 (반복문!)
- 시간 복잡도: n, 빅 오 표기법으로는 O(n)
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
알고리즘2: 1부터 n까지의 합을 구하는 알고리즘2¶
- $\frac { n (n + 1) }{ 2 }$
In [1]:
def sum_all(n):
return int(n * (n + 1) / 2)
In [2]:
sum_all(100)
Out[2]:
시간 복잡도 구하기¶
- 1부터 n까지의 합을 구하는 알고리즘2
- 입력 n이 어떻든 간에, 곱셈/덧셈/나눗셈 하면 됨 (반복문이 없음!)
- 시간 복잡도: 1, 빅 오 표기법으로는 O(1)
어느 알고리즘이 성능이 좋은가요?¶
- 알고리즘1 vs 알고리즘2
- O(n) vs O(1)
이와 같이, 동일한 문제를 푸는 알고리즘은 다양할 수 있음 어느 알고리즘이 보다 좋은지를 객관적으로 비교하기 위해, 빅 오 표기법등의 시간복잡도 계산법을 사용함
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다