Algorithms, Data Analytics

힙

 -> 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

완전 이진 트리

 -> 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙을 사용하는 이유

 -> 1) 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림, 이에 반해 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(log n)이 걸림

 -> 2) 우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

힙 구조

 -> 힙은 최대값을 구하기 위한 최대힙, 최소값을 구하기 위한 최소힙으로 분류

힙의 조건

 -> 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다( 최대힙 )

 -> 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음( 최소힙 )

 -> 완전 이진트리의 형태

힙과 이진 탐색 트리의 공통점과 차이점

 -> 힙과 이진 탐색 트리는 모두 이진 트리임

 -> 힙은 각 노드의 값이 자식 노드보다 크거나 같음

 -> 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼

 -> 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음

      -> 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도, 왼쪽이 클 수도 있음

 -> 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해

알고리즘1 : 1부터 N까지의 합을 구하는 알고리즘

def sum_all(n):

  total = 0

  for num in range(1, n+1):

    total += num

  return total

알고리즘2 : 1부터 N까지의 합을 구하는 알고리즘

def sum_all(n)

  return ((n * (n+1)) / 2)

뭐가 더 빠를까?

알고리즘 1은 시간복잡도가 O(n)

알고리즘 2는 시간복잡도가 O(1)이다.

알고리즘 복잡도 계산이 필요한 이유

 -> 하나의 문제를 푸는 알고리즘은 다양하다, 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

시간 복잡도 : 알고리즘 실행 속도

공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

알고리즘 시간 복잡도의 주요 요소

 -> 반복문이 주된 영향을 미침

알고리즘 성능 표기법

 -> 1) Big O(빅-오) 표기법 : O(N)

  -> 알고리즘 최악의 실행 시간을 표기

  -> 가장 많이, 일반적으로 사용

  -> 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미

 -> 2) Ω(오메가) 표기법 : Ω(N)

  ->오메가 표기법은 알고리즘 최상의 실행 시간을 표기

 -> 3) θ(세타) 표기법 : θ(N)

  -> 세타 표기법은 알고리즘 평균 실행 시간을 표기