자료구조 - 시간복잡도와 공간복잡도

알고리즘이 얼마나 효율적인지 측정하는 기준

• 시간복잡도 : 코드가 얼마나 빠르게 작동하냐.
  시간복잡도가 커지면 코드는 느려지고, 시간복잡도가 낮아지면 코드는 빨라짐.
  
  
• 공간복잡도 : 코드가 얼마나 많은 메모리를 사용하냐.
  공간복잡도가 커지면 메모리를 많이 차지하고, 공간복잡도가 낮아지면 메모리를 적게 차지해.

      보통 코드의 효율성을 얘기할 때 공간복잡도보다 시간복잡도에 더 초점을 맞춰서 얘기하긴해.

 

시간복잡도(Time-complexity)

알고리즘에 사용되는 총 연산횟수. 어떤 알고리즘 안에서 연산을 몇번 하는가? 알고리즘이 진행되는데 걸리는 실행시간이 아니라, 연산횟수라는거에 유의.

sum = 0;    # 여기서 연산 1번
for i in [1, 2, 3, 4]:    # 연산 4번
	sum +=i;
    
# 시간복잡도 = 1 + 4 = 5번(회)

 

randomNumber = 0    # 1번
nums = [1, 2, 3, 4]    # 1번
for i in range(len(nums)):    # for문 안에
	for j in range(len(nums)):    # for문 이니까 4*4 = 16번
    	    randomNumber += nums[i] * nums[j]
        
# 시간복잡도 = 1 + 1+ 16 = 18번(회)

근데, 알고리즘이 좀 복잡해지면 어떻게 계산할까?

 

입력 변수의 크기가 N이라면?

• 입력 변수의 크기 = N
• 코드의 시간 복잡도 = f(N)  <- N에 대한 함수라는 뜻

def doNothing(nums):
	return nums
    
"""
함수 이름처럼 아무것도 안하는 함수
nums의 크기가 n이라고 했을 때 이 함수의 시간 복잡도는?

시간복잡도 = 1
Why? 자세한건 빅오에서 더 설명. 일단 여기선 return의 연산은 1이라고 가정
그래서 이 함수는 return문 하나밖에 없으니까 시간 복잡도는 1"""

def doSomething(nums):
	sum = 0    # 1번
    for num in nums:
    	sum += num    # N번
    return sum    # 1번
    
"""
nums의 크기가 N
sum = 0 과 retrun sum 은 N의 크기와 상관없이 1번씩만 실행돼
N의 크기에 영향을 받는 부분은 for문. nums의 크기가 N이면 sum += num은 N번 실행
시간복잡도 = N+2 """

def doManything(nums):
    allPairs = []    # 1번
    for i in range(len(nums)):    # for문 안에 for문이니까 N * N
        for j in range(len(nums)):    # if-else에서 몇번이 나오는지 보고 N * N 에 곱해줘
            if nums[i] < nums[j]:    # 이 조건에서 1번    
                allPairs.append((nums[i], nums[j]))    # (1) 둘 중 하나가 실행되니까 여기서 1번
            else:
                allPairs.append((nums[i], nums[j]))    # (2) 그래서 N * N * 2
    return allPairs    # 1번
    
"""
nums의 크기는 N
시간복잡도 = 2*N^2 + 2"""

 

Big-O 시간복잡도

Big-O = 시간복잡도 함수의 가장 높은 차수.

 

ex1)  aN + b = O(N)
      : 이 식에서 가장 높은 차수는 N이라는 일차항.

 

왜 N앞에 있는 계수 a는 무시할까? 빅오 자체 정의에 따라서 시간복잡도에 가장 큰 영향을 미친다는 차수항만 고려하기로 했기 때문에. 그래서 차수만 고려하고 계수는 고려 x. 계수가 시간복잡도에 미치는 영향은 차수에 비해 매우 미미해서 그래.

 

ex2) aNlogN + b = O(NlogN)

ex3) aN^2 + bN + c = O(N^2)

def doNothing(nums):
	return nums
    
"""
시간복잡도 = 1
가장 높은 차수는 상수항이니까 이 경우에
Big-O 시간복잡도 = O(1)
N의 크기에 상관없이 항상 일정하다는 얘기이기도 해"""

def doSomething(nums):
	sum = 0    # 1번
    for num in nums:
    	sum += num    # N번
    return sum    # 1번
    
"""
nums의 크기가 N
시간복잡도 = N+2
가장 높은 차수는 N의 일차항이니까
Big-O시간 복잡도 = O(N)
이 경우 시간복잡도는 N의 크기에 비례해서 증가 """

def doManything(nums):
    allPairs = []    # 1번
    for i in range(len(nums)):    # for문 안에 for문이니까 N * N
        for j in range(len(nums)):    # if-else에서 몇번이 나오는지 보고 N * N 에 곱해줘
            if nums[i] < nums[j]:    # 이 조건에서 1번    
                allPairs.append((nums[i], nums[j]))    # (1) 둘 중 하나가 실행되니까 여기서 1번
            else:
                allPairs.append((nums[i], nums[j]))    # (2) 그래서 N * N * 2
    return allPairs    # 1번
    
"""
nums의 크기는 N
시간복잡도 = 2*N^2 + 2
가장 높은 차수는 N^2니까
Big-O 시간 복잡도 = O(N^2)
마찬가지로 N의 값에 따라서 시간복잡도가 증가한다"""

 

Q. 복잡도가 왜 중요한걸까?

잘 와닿지 않을 수 있는데, 시간복잡도가 다른 코드 1, 2를 서로 비교해보면 느낌을 알 수 있어.

	코드 1	코드 2
시간 복잡도	1,000N	2N^2
Big-O	O(N)	O(N^2)

 

 

N	1	10	100	1,000	10,000	...
코드 1	1,000	10,000	100,000	1,000,000	10,000,000	...
코드 2	2	200	20,000	2,000,000	200,000,000	...

N이 1, 10, 100일 때에는 코드 1의 시간복잡도가 훨씬 큰데, N이 증가함에 따라 두 코드간의 시간복잡도 차이가 줄어들어. 그러다가 결국 N이 1,000이상을 넘어가게 되면 코드 2의 시간복잡도가 기하급수적으로 늘어나게 됨. 

 

이걸 그래프로 보면,

0-20까지는 별로 차이가 나지 않지만,  N의 크기가 증가하면 증가할수록 차이가 너무 나게 돼. 보통 알고리즘의 크기는 굉장히 큰 N의 값이 들어온다고 가정하고 성능을 비교해야해. 왜냐면 N에는 어떤 값이 들어올지 모르기 때문에 프로그래머가 예상을 할 수 없잖아. 어떤 값이 들어와도 효율적인 알고리즘을 만들어내려면 N이 아주 큰 값이 들어올 수도 있겠다라고 생각하고 코드를 짜야되는 것.

 

 

Big-O 시간복잡도 계산법칙

1. for / while loop가 한 번 중첩될 때마다 O(N)

for num in nums:
"""
모든 nums의 크기는 N이라고 가정
Big-O 시간복잡도 = O(N)"""

for i in range(len(nums)):
	for j in range(len(nums)):
"""
Big-O 시간복잡도 = O(N*N) = O(N^2)"""

for i in range(len(nums)):
	for j in range(len(nums)):
    	for k in range(len(nums)):
"""
Big-O 시간복잡도 = O(N*N*N) = O(N^3)"""

 

2. 자료구조를 사용하거나, 다른 함수를 호출할 땐 각각의 O(N)을 파악

nums = [2, 8, 19, 37, 4, 5]    # 배열의 자료구조. 배열의 크기 그대로 따라가서
if num in nums:
"""
Big-O 시간복잡도 = O(N)"""

nums = {2, 8, 19, 37, 4, 5}    # nums라는 세트에 대해서, 배열과는 다르게. 세트에 대한 설명은 나중에
if num in nums:
"""
Big-O 시간복잡도 = O(1)"""

nums.sort()
"""
Big-O 시간복잡도 = O(NlogN)"""

여기서 중요한건, 왜 세트는 O(1)이 나왔냐, sort()함수는 왜 O(NlogN)이냐가 아니고, 자료구조나 다른함수를 사용하게 되면 각각의 자료구조나 함수에 필요한 Big-O 시간복잡도를 사용해야한다는 것이 중요한 거.

 

3. 매번 절반씩 입력값이 줄어들면 O(logN)

ex) 매번 실행이 될 때마다 배열의 크기가 반씩 줄어들고 있어. 8-> 4-> 2-> 1 이렇게. N의 크기가 8이고 이 법칙에 따라서 실행횟수는 log8 = 3이됨. 실제로도 저 화살표 수대로 3번의 연산이 이루어졌잖아. 그래서 입력값이 절반씩 줄어들면 O(logN)의 시간복잡도를 가진다고 알고있으면 됨.

 

 

 

공간복잡도(Space-complexity)

알고리즘에 사용되는 메모리 공간의 총량. 

 

Big-O 공간복잡도

a = 1    # 1이라는 값 하나를 a라는 변수에 저장하는거
"""
Big-O 공간복잡도 = O(1)"""

a = [num for num in nums]
"""
nums의 크기를 N이라고 했을 때
nums 안에 있는 모든 num에 대해서 하나씩 대응하는 원소를 이 배열 안에 넣는다는 거니까
Big-O 공간복잡도 = O(N)"""

a = [[num for num in nums] for num in nums]
"""
nums의 크기를 N이라고 했을 때
nums 안에 있는 모든 num에 대해서 하나씩 대응하는 원소를 이 배열 안에 넣는거 -> N
또 그 num에 대해서도 nums만큼 반복이되니까 -> N
Big-O 공간복잡도 = O(N^2)"""

공간복잡도는 이정도만 알아도 된다고함....