시간복잡도

알고리즘 문제해결 전략 Chapter 4

개관

• 알고리즘
  • 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법
  • 문제를 해결할 때 한 가지 방법을 명료하게 써 놓아야 함
  • 가능한 한 명료하고 모호한 표현을 써야 함
• 알고리즘을 평가하는 요소
  • 두가지 요소 
    • 시간: 적은 시간을 사용
    • 공간: 적은 공간을 사용 - 더 작은 용량의 메모리를 사용
  • 서로 상충되는 경우가 많기 때문에, 메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서 메모리 사용량을 줄일 수 있음

 

알고리즘의 시간 복잡도 분석

• 속도 비교 방법
  • 직관적으로는 수행 시간 측정하기
    • but, 수행시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 수 많은 요소에 의해 바뀔 수 있음
    • 심지어, 어떤 문자열을 구현했는지, 함수인자를 어떻게 넘겼는지(주소만 넘기면 접근이 빠름)에 따라 성능 차이가 남
    • 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못함
  • 반복문이 지배한다
    • 자동차 vs 자전거
      • 무지 짧은 거리를 갈 경우, 자전거가 적은 시간을 소요하지만, 거리가 늘어나면 자동차가 훨씬 적은 시간을 소요
        • 이는, 준비 시간에 소요되는 시간은 크게 무의미하다.
        • 한 가지 항목이 전체의 대소를 좌지우지하는 것을 지배한다(dominate)고 표현
• 선형 시간 알고리즘
  • 다이어트 현황 파악: 이동 평균 계산하기
    • 이동 평균: 주식의 가격, 연간 국내 총생산(GDP), 몸무게 등 시간에 따라 변화하는 값들을 관찰 할 때 유용하게 사용
    • N개의 측정치가 주어질 때, 매달 M달 간의 이동평균을 계산하는 프로그램
      • M*(N-M+1) 반복됨
    • 하지만, 이게 누적될 경우 많은 시간을 소요하기 때문에, 직전 값에서 첫번째 값을 빼고 추가되는 값을 더하는 방식으로 하면 시간이 적게 소요됨
      • M - 1 + (N - M + 1) = N
  • 선형 이하 시간 알고리즘
    • 이진 탐색
      • 정렬이 되었을 때, 원하는 값을 찾기 위해서는 logN만큼의 시간이 소요된다.
        • 하지만, 정렬에 많인 시간을 소요하기 때문에 여러번의 이진 탐색이 이뤄진다면 더 좋을 것이다.
  • 지수 시간 알고리즘
    • 다항 시간 알고리즘
      • 다항식: N의 거듭제곱들의 선형 겨합으로 이루어진 식들
    • 예) 알러지가 있는 친구들에게 음식을 대접하기 위해서 최소한 하나씩 먹으려면 최소 몇가지의 음식을 먹어야 하는가?
      • 모든 답 후보를 평가해야됨
      • 일일이 모든 답을 고려해야 함
      • 음식의 모든 목록을 만드는 과정을 여러 개의 결정으로 나누어, 첫 번째 요리를 만들지 말지 결정하고, 그 다음엔 두 번째 요리를 만들지 말지를 결정하는 식으로 해서 식사할 수 있는 목록들만을 골라낸 뒤 가장 음식의 수가 적은 목록을 찾아내기
      • 이 때, 사용하는 가장 편한 방법은 재귀 호출
    • 지수 시간 알고리즘
      • 모든 답을 한번씩 다 확인하기 떄문에 전체 걸리는 시간은 만들 수 있는 답의 수에 비례하게 됨
        • M가지의 음식마다 만든다/안만든다 두 선택지 -> 2^M개의 답이 있음
    • 지수 시간 알고리즘은 많은 시간을 소요하기 때문에 다항 시간 알고리즘과 적절하게 잘 활용해서 시간을 줄여야 함
    • 소인수 분해의 수행시간
      • 자연수 N이 주어질 때 소인수분해 결과: N이 1이 될 때까지 간으한 모든 수를 N을 나눠보기
      • 반복문의 실행횟수 자체는 N - 1이기 때문에 선형 시간이 걸린다고 생각하기 쉬움
        • 하지만, 입력의 개수와 메모리에서 차지하고 있는 공간이 직접적으로 비례하기 때문에 입력이 커지면 숫자를 저장하는 메모리 공간이 증가할 것이고, 비트 수에 따른 계산의 시간이 늘어날 것이다.
        • 비트수로 정의할 경우, 지수 시간 소요될 것
  • 시간 복잡도
    • 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
      • 기본적인 연산
        • 두 부호 있는 32비트 정수의 사칙연산
        • 두 실수형 변수의 대소 비교
        • 한 변수에 다른 변수 대입하기
      • 기본 연산 x
        • 정수 배열 정렬
        • 두 문자열이 같은지 확인
        • 입력된 수 소인수 분해하기
    • 시간 복잡도가 낮다고 적은 시간을 소요한 것은 아님
      • 입력 데이터가 적을 경우, 시간복잡도가 높아도 적은 시간을 소요할 수 있음
    • 입력의 종류에 따라 수행 시간이 달라지기 때문에 최선/최악/평균에 대한 수행 시간을 각각 계산
    • 점근적 시간 표기: O 표기
      • 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법
      • 최악의 수행 시간을 알아낸 것은 아님
    • 시간 복잡도의 분할 상환 분석
      • 단순히 반복문의 개수를 세는 것으로만 결정하지는 않음
        • 예) 전체 작업에 걸리는 시간이 일정한 경우, 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같음
  • 수행 시간 어림짐작하기
    • 주먹구구 방법
      • 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.
      • 고려해야 할 사항들
        • 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
        • 반복문의 내부가 복잡한 경우
        • 메모리 사용 패턴이 복잡한 경우
        • 언어와 컴파일러의 차이
        • 구형 컴퓨터를 사용하는 경우
  • 계산 복잡도 클래스: P, NP, NP-complete
    • P문제
      • 다항 시간ㅇ알고리즘이 존재하는 문제들의 집합
        • 예) 정렬문제: 다항 시간 알고리즘이 수업싱 많이 존재
    • NP문제
      • 어려운 문제
      • 주어진 문제가 기준 이상으로 어려운지 판정하기가 쉽지 않음
      • 문제 A가 문제 B이상으로 어렵다고 말하려면, A를 푸는 가장 빠른 알고리즘이 B를 푸는 가장 빠른 알고리즘 이상의 시간이 걸려야 함
      • 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법 사용
        • 한 문제를 다른 문제로 바꿔서 푸는 방법
      • 어려운 문제의 기준이 되는 것: SAT문제
        • N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수값들의 조합을 찾는 문제
        • NP문제 이상으로 어려움
      • NP문제: 답이 주어졌을 때, 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미
        • 예) 부분 집합 합 문제
    • NP-Hard
      • SAT가 모든 NP 문제 이상으로 어렵다는 말은 SAT를 다항 시간에 풀 수 있으면 NP문제들을 전부 다항 시간에 풀 수 있음
      • 다항 시간에 푸는 방법이 없을 경우
    • NP-complete
      • NP-Hard + NP
    • P = NP?
      • 증명되지 않음
  •