자료구조와 알고리즘 6강

자료구조와 알고리즘 6강

Posted by 동식이 블로그 on September 18, 2019

6강: 알고리즘의 복잡도

알고리즘의 복잡도 (Complexity of Algorithms)

알조리즘의 복잡도란?

  • 문제 풀이의 방식이 얼마나 복잡하냐 단순하냐를 나타내는 말이 아니다

  • 알고리즘이 실행함에 있어, 문제의 크기(일반적으로 데이터 원소의 개수)가 커짐에 따라서 얼마나 큰 시간(또는 공간)을 요구하느냐를 뜻함
  • 시간 복잡도(Time Complexity)

    • 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 시간이 어떤 양상으로 증가하는가를 말한다
  • 공간 복잡도(Space Complexity)

    • 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 기억 공간(메모리)의 필요가 어떤 양상으로 증가하는가를 말한다
  • 이 강의에서는 시간 측면에서 논의
평균 시간 복잡도와 최악 시간 복잡도
  • 평균 시간 복잡도(Average Time Complexity)
    • 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
  • 최악 시간 복잡도(Worst-case Time Complexity)
    • 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

알고리즘의 복잡도 표현

  • 점근 표기법(asymptotic notation)을 흔히 이용
  • 그 중 Big-O notation 이라고 불리는 것을 많이 이용하는데 , 영문 대문자 O 를 이용하여 기호로 표현하기 때문에 붙은 이름이다.
    • 이 표기법은 함수의 증가 양상을 대강 파악할 수 있도록 하는데 목적이 있다.
    • 예를들어 데이터 원소의 개수가 n_개라고 할 때, _O(n) 복잡도를 가지는 알고리즘은 원소의 개수에 비례하여 소요 시간이 증가한다.
    • 계수는 그다지 중요하지 않다

선형 시간 알고리즘 - O(n)

  • _n_개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용
  • Average case: O(n)
  • Worst case : O(n)
  • 모든 수를 다 돌아봐야 하기 때문에 동일하다

로그 시간 알고리즘 - O(logn)

  • _n_개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용
  • O(logn)의 복잡도를 가지고 문제를 풀 수 있으면 굉장히 효율적이다

이차 시간 알고리즘 - O(n^2)

  • 삽입 정렬
  • 정렬할 요소를 정렬된 요소 중 어느곳에 넣어서 정렬된 상태를 유지할지
  • Best case: O(n)
    • 이미 정렬이 된 상태
  • Worst case: O(n^2)
    • 역순으로 늘어서 있을 때

보다 나은(낮은) 복잡도를 가지는 정렬 알고리즘

  • 병합정렬 - O(nlogn)
    • 입력 패턴에 따라 정렬 속오데 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음
      1. 정렬할 데이터를 반씩 나누어 각각을 정렬시킴 : O(logn)
      2. 정렬된 데이터를 두 묶음씩 한데 합친다 : O(n)
      3. 전체적으로 O(nlogn)이 된다

꽤나 복잡한 문제

  • 배낭 문제(Knapsack Problem)
  • 모든 경우의 수를 다 해볼 경우 O(n^2)
  • DP를 이용하면 간단하게 풀 수 있다.
요약
  • 병합정렬, 즉 divide-and-conquer : O(nlogn)
  • 이진탐색 : O(logn)
  • 선형탐색 : O(n)
  • N*N행렬의 모든 원소쌍 비교 : O(n^2)
  • 행렬 A, B의 곱인 C의 행렬 계산 : O(n^3)


본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.

출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?