- 정수의 절대값 구하기
- 방법1 : 정수값을 제곱한 값에 다시 루트를 씌우기
- 방법2 : 정수가 음수인지 확인해서 음수일 때만 -1을 곱하기
{% hint style="info" %} 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 복잡도를 정의하고 계산한다. {% endhint %}
- 시간 복잡도 : 알고리즘 실행 속도
- 공간 복잡도 : 알고리즘이 사용하는 메모리 사이
{% hint style="info" %} 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 한다. {% endhint %}
{% hint style="info" %} 반복문이 지배합니다. {% endhint %}
- 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배한다.
- Big O (빅-오) 표기법: O(N)
- 알고리즘 최악의 실행 시간을 표기한다.
- 가장 많이 / 일반적으로 사용한다.
- 아무리 최악의 상황이라도 이 정도의 성능은 보장한다는 의미이기 때문이다.
- Ω (오메가) 표기법 : Ω(N)
- 오메가 표기법은 알고리즘 최상의 실행 시간을 표기한다.
- Θ (세타) 표기법 : Θ(N)
- 세타 표기법은 알고리즘 평균 실행 시간을 표기한다.
{% hint style="info" %} 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중 최악의 시간인 Big-O 표기법을 중심으로 익히면 된다. {% endhint %}
- 빅 오 표기법, Big-O 표기법이라고도 부른다.
- O(입력)
- 입력 n에 따라 결정되는 시간 복잡도 함수
- O(1), O(log n), O(n), O(nlog n), O(n^2), O(2^n), O(n!) 등으로 표기한다.
- 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다.
- O(1) < O(log n) < O(n) < O(nlog n) < O(n**2) < O(2**n) < O(n!)
- 참고, log n의 베이스는 2 - log2n
- O(1) < O(log n) < O(n) < O(nlog n) < O(n**2) < O(2**n) < O(n!)
- 단순하게 입력 n에 따라 몇 번 실행이 되는지를 계산하면 됩니다.
- 표현식에 가장 큰 영향을 미치는 n의 단위로 표기합니다.
- n이 1이든 100이든, 1000이든 실행을
- 무조건 2회(상수회) 실행한다 : O(1)
- n에 따라, n번, n + 10번 또는 3n + 10번 등 실행한다 : O(n)
- n에 따라, n^2번, n^2 + 1000번 또는 100n^2 - 100번 등 실행한다 : O(n^2)
- 빅 오 입력값 표기 방법
- e.g.)
- 만약, 시간 복잡도 함수가 2n^2 + 3n 이라면
- 가장 높은 차수는 2n^2
- 상수는 실제 큰 영향이 없음
- 결국 빅 오 표기법으로는 O(n^2)
- 만약, 시간 복잡도 함수가 2n^2 + 3n 이라면
- e.g.)
- 합을 기록할 변수를 만들고 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까지의 합을 구하는 알고리즘1
- 입력 n에 따라 덧셈을 n번 해야 한다. (for 반복문)
- 시간 복잡도 : n / Big-O : O(n)
- n( n + 1) / 2
def sum_all(n):
return int(n * (n + 1) / 2)
sum_all(100) // 5050
- 1부터 n까지의 합을 구하는 알고리즘2
- 입력 n이 어떻든 간에 덧셈/곱셈/나눗셈 하면 된다. ( 반복문 X )
- 시간 복잡도 : 1 / Big-O : O(1)
- 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
- 시간 복잡도 : 얼마나 빠르게 실행되는지
- 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지
{% hint style="info" %} 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다. {% endhint %}
- 통상 둘 다 만족시키기는 어려움.
- 시간과 공간은 반비례적 경향이 있다.
- 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선시된다.
- 그래서, 알고리즘은 시간 복잡도가 중심이 된다.
- 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많다.
- 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라 공간 복잡도도 제약 사항이 있는 경우가 있다.
- 또한, 기존 알고리즘 문제에 영향을 받아서 면접시에도 공간 복잡도를 묻는 경우가 있다.
- 최악의 경우 시간 복잡도: O(N)
- 최악의 경우 공간 복잡도: O(N)
{% hint style="info" %} 현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있다. {% endhint %}
- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.
- 총 필요 저장 공간
- 고정 공간( 알고리즘과 무관한 공간 ) : 코드 저장 공간, 단순 변수 및 상수
- 가변 공간( 알고리즘 실행과 관련있는 공간 ) : 실행 중 동적으로 필요한 공간
- S(P) = c + Sp(n)
- c : 고정 공간
- Sp(n) : 가변 공간
{% hint style="info" %} Big-O 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다. {% endhint %}
- 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 된다.
- 이를 Big-O 표기법으로 표현할 수 있으면 된다.
- n! 구하기.
- n! = 1 x 2 x ... x n
- n의 값에 상관없이 변수 n, 변수 fac, 변수 index만 필요하다.
- 공간 복잡도는 O(1)
{% hint style="info" %} 공간 복잡도 계산은 실제 알고리즘 실행시 사용되는 저장공간을 계산하면 된다. {% endhint %}
def factorial(n):
fac = 1
for index in range(2, n + 1):
fac = fac * index
return fac
print(factorial(3)) # 6
- n! 구하기.
- n! = 1 x 2 x ... x n
- 재귀함수를 사용하였으므로 n에 따라 변수 n이 n개가 만들어지게 된다.
- factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 된다.
- 공간 복잡도는 O(N)
- 재귀함수가 호출될 때마다 n이라는 변수가 n개 만들어진다.
def factorial(n):
if n > 1:
return n * factorial(n - 1)
else:
return 1
print(factorial(3)) # 6