1.공간복잡도&시간복잡도

※공간복잡도&시간복잡도

1. 공간 복잡도(Space Complexity) : 알고리즘에 사용되는 메모리 공간의 총량

 

예를 들어, 크기가 N인 배열을 만든다고 가정하면 공간 복잡도가 O(N)이 되고 NxN인 배열을 만들면 O(N²)이 됩니다. 함수의 재귀적인 호출의 경우 스택 공간도 고려해야 합니다.

!!인자로 받은 데이터는 제외, 함수내에서 사용할경우 포함

1) def Num1(a,b): --공간복잡도 0

return a+b

2) def Num2(arr,n): --공간복잡도 arr+(n,i,result) => n+3

result = 0

for i in range(n):

result += arr[i]

return result

3) 재귀함수(recursion)는 깊이 * (변수갯수+복귀주소(1)) 로 공간복잡도를 계산해야한다.

2. 시간 복잡도(Time Complexity) : 알고리즘에 사용되는 연산횟수의 총량

1) def Num3(n,m):

result = 0

for i in range(n): # (n-1)

for j in range(m): #(n-1)*(n-1)

result += i+j

return result

실행횟수를 모두 더하면 n²-n 이다. 그중에서 최고차항만 가지고온다. Big-O는 O(n²)이다.

Regular        Big-O

2                O(1)

2n + 10       O(n)

5n²+4n+5  O(n²)

O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.

O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.

O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.

O(n²) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.

O(n³) – 3차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 세제곱입니다.

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)

공간복잡도는 메모리 사용량에 대한 분석결과이고 시간복잡도는 속도에 대한 분석결과이다.

 

참조:https://m.blog.naver.com/PostView.nhn?blogId=demonic3540&logNo=221229805234&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F,

https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/