다음은 어떤 프로그램의 성능을 측정할때 고려해야 할 것들이다.

1. 입력 데이터의 크기
2. 프로그램이 동작하는 하드웨어의 성능
3. 운영체제의 성능
4. 프로그램 빌드하는 컴파일러의 성능
5. 기타 비동기 로직들..

프로그램은 이런 다양한 환경에서 돌아갈 수 있기 때문에, 프로그램의 성능을 정확히 측정하는것은 불가능하다.

따라서 프로그램 성능은 시간(분, 초)이라는 절대적인 기준으로 측정하는 것이 아닌, 기본 연산의 실행 횟수로 수행 시간을 측정한다.

1. 시간복잡도 (Time complexity)

프로그램 수행 시간(기본 연산의 실행 횟수)을 점근적 표기법으로 표현한것.

점근적 표기법

필수적인 부분에 집중하고 불필요한 상세들은 무시하는 표기법

1) 상수계수 무시

for i in range(6):
	print(i)

위 알고리즘의 시간 복잡도는 6O(n)이지만, O(n)으로 표기한다.

n이 무한에 수렴할수록 6이라는 계수는 의미가 없어지기 때문이다.

2) 가장 큰 항에 집중

for i in range(10):
	for j in range(10):
		print(i+j)
		
for i in range(50):
	print(i)

위 알고리즘의 시간복잡도는 O(n² + n)이지만, O(n²)로 표기한다.

3) 상수 무시

어떤 알고리즘의 시간복잡도가

O(n² + 100) → O(n² + 100)

O(3logn + 100000) → O(logn)

일때, 무의미한 상수는 무시한다.

2. Big-O

시간 복잡도에는 세가지 경우가 있다.

1. 최선의 경우(Best Case)
   1. 빅 오메가 표기(Big-Ω)
2. 최악의 경우(Worst Case)
   1. 빅 오 표기(Big-O)
3. 평균적인 경우(Average Case)
   1. 빅 세타 표기(BIg-θ)

어떤 상황에서도 최소한의 성능을 측정해야 하기 때문에 최악의 경우를 기준으로 시간복잡도를 계산한다.

시간 복잡도 계산

앞서 언급한 대로 시간 복잡도는 기본 연산 실행 횟수에 따라 계산된다.

n = input()      #입력 1회
sum = 0          #대입연산자 1회
for i in range(n)       #반복문 n회
	sum += i       #사칙연산 n회
	
print(sum)       #출력 1회

위 알고리즘의 시간복잡도는 O(2n + 3).

점근적 표기로 인해 위 알고리즘의 시간복잡도는 O(n)이 된다.

다음은 Big-O 표기법의 종류이다.

O(1) → O(logn) → O(n) → O(nlogn) → O(n²) → O(2ⁿ)순으로 실행시간이 느리다.

O(1)

입력 크기에 상관없는 일정한 연산 수행

print("hello world!")

O(logn)

입력크기가 커질때 logn에 비례해서 증가하는 경우

while i<=n:
	print(i)
	i=i*2

i값이 반복할때 마다 2배로 증가하기 때문에 이것을 k번 반복하면 2^k <= n이 될때 반복문이 종료된다.

k번 반복횟수를 구하기위해 양변에 로그를 취하면 k = logn이 된다.

따라서 이 연산의 시간복잡도는 O(logn)이 된다.

O(n)

입력n이 증가함에 따라 연산횟수역시 n만큼 증가하는 경우

n = input()
for i in range(n):
	print(i)

반복문에서 입력받은 n만큼 반복연산되기때문에 O(n)이된다.

O(nlogn)

n = input()
m = input()
for i in range(n):
	while j<=m:
		print(j)
		j=j*2

선형시간(O(n))인 반복문안에 로그시간O(logn)이 포함되어있으므로
O(nlogn)인 시간복잡도를 가지게 된다.

O(n²)

for i in range(n):
	for j in range(m):
		print(i+j)

반복문이 중첩되어있으면 O(n²) 시간복잡도를 가지게 된다.

O(2ⁿ)

def func(int n):
	if(n<=1)
		return n
	return func(n-2)+func(n-1)

피보나치 수열(앞의 두 수를 더해 다음 수가 나오는 수의 배열(1, 1, 2, 3, 5, 8, 13, 21, …))을 구하는 알고리즘.

함수가 한번 호출하면 함수가 2번의 재귀함수가 호출된다. 즉, 입력값이 증가함에 따라 실행시간이 2배로 증가하기 때문에 O(2ⁿ)의 시간복잡도를 가지게 된다.

3. 공간복잡도

공간 복잡도는 알고리즘에서 사용하는 메모리 양.
공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념.
보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간이다.
그렇기 때문에 입력 공간(input size)을 고려하지 않는다.

대규모 데이터를 처리하거나 메모리가 제한된 환경에서 중요하지만 . 단순 알고리즘 공부할 시 메모리는 그닥 중요한 요소는 아니기 때문에 일단 넘어간다.

공간복잡도 역시 Big-O표기법을 따라사용한다.

def sum_array(a, n):
    x = 0
    for i in range(n):
        x = x + a[i]
    return x

a= n * 4byte(int)

n = 4byte(int)

x = 4byte(int)

i = 4byte(int)

→ O(4n + 12) = O(n)공간복잡도를 가짐