개요
알고리즘을 해결할 때는 복잡도가 굉장히 중요하다. 복잡도는 시간복잡도와 공간복잡도로 나뉘어지는데 하나씩 공부해보도록 하자. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다.
시간복잡도
시간 복잡도란?
입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복횟수를 중점으로 측정된다.
👉 시간복잡도는 시간을 재야할까?
아니다. 로직에 걸리는 시간은 측정하는 컴퓨터 사양에 영향을 받기 때문에 시간 복잡도를 ‘시간’으로 측정하기에는 무리가 있다.
import math
import time
start = time.time()
math.factorial(100000)
end = time.time()
print(end-start)
>> 0.16011404991149902
따라서 알고리즘이 주어진 입력크기를 기반으로 어떤 로직이 몇 번 반복되었는가를 중점으로 설명할 수 있다.
예를 들면, 다음 코드의 시간복잡도는 무엇일까?
for i in range(0, 10):
for j in range(0, N):
for k in range(0, N):
print(i, j, k)
for i in range(0, N):
print(i)
print(i, j, k)라는 로직이 만큼 반복되고print(i)가 만큼 반복되고 있으므로,
- 시간복잡도는 이다.
빅오표기법(Big-O notation)
빅오표기법
복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법이다.
👉 빅오 표기법만 있을까?
아니다. 컴퓨터 과학에서 점근 표기법은 알고리즘이 얼마나 효율적인지 따져보기 위한 방법이다. Big-O notation, Big-Ω notation, Big Θ-notation 등이 있고 가장 많이 쓰이는 방법은 Big-O notation 이다.
예를 들어서, 다음과 같은 시간복잡도에서 가장 많은 영향을 끼치는 항은 무엇일까?
바로 이다.
n을 신경쓰지 않는 이유는 n이 증가한다고 해도 이 월등히 크게 증가하기 때문이다.
그래서 의 빅오표기법은
빅오 표기법 복잡도 비교
빅오 표기법에 따른 복잡도 차트를 보면 얼마나 효율적인 알고리즘인지 파악할 수 있다.
알고리즘 공부할 때 마다 나오니까 아래 차트에 나와 있는 순서는 꼭 외워놓자. (기본적인 것)
상수시간 시간복잡도는 O(1)
상수시간의 시간복잡도는 입력크기와 상관없이 일정한 시간복잡도를 가지는 것을 말한다.
예를 들어, 다음과 같은 로직은 모두 의 시간복잡도를 가진다.
- 입력과 출력
import sys
a = sys.stdin.readline()
b = input()
>> 입력값이 많을 땐, input() 보다 sys.stdin.readline()이 빠르다.
print('출력')
- 곱하기, 나누기, 나머지연산, 빼기 등
- 간단한 비교 if 문
if n == 2:
- 배열의 인덱스 참조
a[2] = [1,2,3]
b = c[2]
문제로 연습하는 시간복잡도
- 다음 코드의 시간복잡도는?
a = 0
n = int(input())
for i in range(0, n):
for j in range(0, i):
a += (i+j)
print(a)- 시간복잡도는
- 다음 코드의 시간복잡도는?
N, M = map(int, input())
def solve(N, M):
a = 1
for i in range(0, N):
a *= i
for j in range(0, M):
a *= j
print(a)
solve(N, M)- 시간복잡도는
- 다음 코드의 시간복잡도는?
N = int(input())
a = []*1004
def go(l, r):
if l==r:
return a[l]
mid = (l+r) // 2
sum = go(l, mid) + go(mid+1, r)
return sum
for i in range(1, N+1):
a[i-1] = i
sum = go(0, n-1)
print(sum)- 시간복잡도는
시간복잡도의 존재 이유는 효율적인 코드의 척도!
시간복잡도는 효율적인 코드로 개선하는데 쓰이는 척도가 된다.
이 부분은 문제를 풀 때 매우 중요하다. 항상 문제를 보고 어떻게 풀어야 할지 생각한 후 그 로직의 시간복잡도를 계산하고 시간초과가 예상된다면, 시간 복잡도를 줄일 수 있는 다른 방법을 생각해야 코딩테스트를 통과할 수 있다.
문제를 풀 때 이 부분을 꼭 염두하여 풀어보자.
자료구조의 시간복잡도
어떤한 로직을 생각하고 그 로직에 알맞는 자료구조를 선택할 때 기준이 되는 것이 자료구조의 시간복잡도이다.
예를 들어, k번째 요소를 계속해서 탐색해야 하는 문제에서는 배열과 연결 리스트 중 누가 효율적일까?
바로 배열이다.
이런 생각을 자연스럽게 하기 위해서는 자주 쓰이는 자료구조들의 시간복잡도가 대략적으로 얼마인지 머릿속에 있어야 한다.
👉 자주 쓰이는 자료구조
- 배열
- 스택
- 큐
- 연결리스트
- 해시 테이블
- 이진탐색트리(Binary Search Tree)
이 자료구조에 대해서 차근차근 정리해서 머릿속에 집어넣을 예정이다.
이 밖의 자료구조의 시간복잡도는 다음의 표를 참고할 수 있다.
공간복잡도
공간복잡도
입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양을 말한다.
배열, 집합, 리스트 등 요소를 담는데 필요한 공간의 양으로 어떤 입력 N이 들어왔을 때 몇 바이트의 공간이 필요한지 빅오표기법으로 나타낼 수 있다.
👉 시간복잡도와 공간 복잡도를 둘 다 만족시킬 수 있을까?
둘 다 만족시키기는 아주 어렵다. 왜냐하면 시간과 공간은 반비례적인 경향이 있기 때문이다. 최근 대용량 시스템이 보편화되면서 공간보다는 시간 복잡도가 우선이 되고 있다.
공간복잡도 계산
실제 알고리즘이 동작하는데 사용되는 저장 공간을 계산하고 이를 빅오 표기법으로 표기한다.
예를 들면,
def factorial(n):
fac = 1
for index in range(2, n+1):
fac = fac * index
return fac
factorial(3)
팩토리얼을 구하는 함수이다.
재귀함수가 아닌 반복문을 사용해 구현되어 있는데 n에 상관없이 변수 fac과 index의 공간만이 필요하다.
따라서 공간 복잡도는,
다른 예제로는,
def factorial(n):
if n>1 :
return n * factorial(n-1)
else:
return 1
factorial(3)
팩토리얼을 재귀함수를 사용해 구하는 코드다.
재귀함수는 호출할 때 마다 n에 따라서 변수 n의 공간이 만들어지게 된다.
따라서 이 때 공간 복잡도는,
공간복잡도를 참고한 문제 풀이 방법
코딩테스트 문제를 보면 문제에 입력의 범위가 나와있기도 하고 그림처럼 메모리 제한이 나와있다.
이런 힌트를 통해 공간과 시간을 고려해서 적절한 풀이 알고리즘을 선택할 수 있어야 한다.
예를 들면, 이진탐색과 펜윅트리 중 어떤 알고리즘을 선택하는지 고민하는 것이 있다.
그러한 노하우는 자료구조와 알고리즘을 공부하면서 늘려야하고 이것을 기록해놓을 예정이다.
참조
https://ratsgo.github.io/data structure&algorithm/2017/09/13/asymptotic/
Uploaded by N2T
