Algorithm

 

시간 복잡도

• 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데에 연산이 몇 번 이루어지는 지를 숫자로 표기한 것

BigO

• 시간 복잡도 함수에서 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간 복잡도를 표기하는 방법

공간 복잡도

• 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다.
• 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
• 고정 공간
  • 입력과 출력의 홋수나 크기와 관계없는 공간의 요구
  • 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수
• 가변 공간
  • 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간
  • 동적으로 필요한 공간
• Ex
  • 위의 경우에 stack에 1부터 n까지 쌓이므로 O(n)

  int factorial(int n)
  {
      int i = 0;
      int fac = 1;
      for(i = 1; i <= n; i++)
      {
          fac = fac * i;
      }
      return fac;
  }

  • 위의 경우엔 stakc에 n과 i, factorial 변수만 저장되므로 O(1)
• int factorial(int n) { if(n > 1) return factorial(n - 1) * n; else return 1; }

DFS

• 깊이 우선 탐색
• 모든 노드를 방문하고자 하는 경우에 선택
• 단순 검색 속도 자체는 BFS보다 느리다
• 순환 알고리즘 형태
• 그래프 탐색의 경우 어떤 노드를 방문했었는지를 검사해야한다.
  • 그렇지 않을 경우 무한 루프 가능성이 있음

BFS

• 넓이 우선 탐색
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택
• DFS보단 좀 더 복잡하다
• 재귀적으로 동작하지 않는다.
• 큐(Queue)를 사용한다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지를 검사해야한다.
  • 그렇지 않을 경우 무한 루프 가능성이 있음

정렬 알고리즘

Name	Best	Avg	Worst	Run-time (정수 60000개)
삽입정렬	n	n^2	n^2	7.438
선택정렬	n^2	n^2	n^2	10.842
버블정렬	n^2	n^2	n^2	22.894
셸정렬	n	n^1.5	n^2	0.056
퀵정렬	nlogn	nlogn	n^2	0.014
힙정렬	nlogn	nlogn	nlogn	0.034
병합정렬	nlogn	nlogn	nlogn	0.026

버블정렬

• n-1, n-2 ... 1 => n(n - 1) / 2 => O(n^2)

퀵정렬

• 분할, 정복, 결합

• 

Reference

• https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html