Algorithms, Data Analytics

알고리즘 계산 복잡도는 두 가지 척도로 표현

 -> 1) 시간 복잡도 : 얼마나 빠르게 실행되는지

 -> 2) 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지

통상 둘 다 만족시키기는 어려움

 -> 시간과 공간은 반비례

 -> 최근 대용량 시스템이 보편화, 공간 복잡도 보다는 시간 복잡도가 우선

 -> 그래서 시간 복잡도가 중심

공간 복잡도 대략적인 계산은 필요함

 -> 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음

 -> 그래서 기존 알고리즘 문제에 시간 복잡도 뿐만 아니라, 공간 복잡도 제약이 있는 경우가 있음

 -> 또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 묻는 경우도 있음

공간 복잡도 예제1

N 팩토리얼 구하기

 -> N! = 1 x 2 x ,,, x N

N에 값에 상관 없이 변수 n, fac, index만 필요함

공간 복잡도는 O(1)

공간 복잡도 계산은 실제 알고리즘 실행시 사용되는 저장공간을 계산하면 됨

def factorial(n):

   fac = 1

   for index in range(2, n+1):

      fac = fac * index

   return fac

공간 복잡도 예제2

재귀 함수를 사용하였으므로, n에 따라 변수 n이 n개가 만들어지게 됨

 -> factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨

 -> 공간복잡도는 O(n)

def factorial(n):

   if n > 1:

      return n * factorial(n-1)

   else:

      return 1

앞에서 구현했던 힙구조를 다시 구현해보았다.

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def insert(self, data):
        if (len(self.heap_array) <= 1):
            self.heap_array.append(None)
            self.heap_array.append(data)
            
        self.heap_array.append(data)
        inserted_idx = len(self.heap_array) - 1
        parent_idx = inserted_idx // 2

        while (self.heap_array[inserted_idx] > self.heap_array[parent_idx]):
            
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
            parent_idx = inserted_idx // 2
            
            if inserted_idx <= 1:
                break

수업 들었던 내용을 생각하며 구현해봤다.

강사님은 move_up이라는 메소드를 활용했는데 메소드 없이 구현해보았다.

돌아가긴 잘 돌아 가는듯

힙 구조를 구현해보았다.

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        
        parent_idx = inserted_idx // 2
        
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        
        else:
            return False
        
    def insert(self, data):
        if (len(self.heap_array) == 0):
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        
        self.heap_array.append(data)
        
        inserted_idx = len(self.heap_array) - 1
        
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
            
        return True

트리 구조를 덜 복잡하게 하기 위해서 root node의 idx를 1로 만들어준다.

그러기 위해서 리스트의 0번째에 None을 넣어주었다.

move_up은 최대힙 구현시에 root node 보다 큰 값이 들어올 경우 root 노드까지 끌어오는 역할을 한다.

insert 메소드의 첫번째 if문은 혹시나 힙에 아무것도 들어있지 않을 경우를 대비한 방어코드이다.

힙의 0번째에 None을 넣었으므로 방금 삽입된 데이터의 위치는 전체 힙의 길이에서 1을 뺀 값이다.

move_up 함수가 True를 결과값으로 내는 한 while은 계속 돌아간다.

move_up 함수가 True를 낸 다는 의미는 자식 노드가 부모 노드보다 크다는 의미이다.

이 경우 자식 노드와 부모 노드의 위치를 바꿔준다.

그리고 그 상위에 있는 부모 노드와 비교를 위해서 inserted_idx의 값에 전에 있던 부모 노드의 위치 값을 넣어준다.