TIL-211214

Time Complexity

• 시간복잡도: 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 걸리는 시간

  • 효율적인 알고리즘은 시간복잡도를 최소화한 알고리즘을 구성했다는 이야기

• 시간복잡도의 표기법: Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타)

  • 시간복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법

• Big-O 표기법: 가장 자주 사용되는 표기법, 최악의 경우를 고려하는 방법

  • O(1): constant complexity, 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있음
    
  • O(n): linear complexity, 입력값의 증가에 시간 또한 같은 비율로 증가하는 것을 의미
    
  • O(log n): logarithmic complexity, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가짐
    
    • BST는 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬
    • Up & Down game
  • O(n2): n의 2승, quadratic complexity, 입력값의 증가에 시간이 n제곱수의 비율로 증가하는 것을 의미
    
    • n3, n5의 경우도 모두 O(n2)로 표기함
  • O(2n): 2의 n승, exponential complexity, Big-O 표기법 중 가장 느린 시간복잡도를 가짐
    
    • O(n!): 재귀로 구현하는 피보나치 수열이 대표적
  • 데이터 크기에 따른 시간복잡도

  데이터 크기 제한	예상되는 시간복잡도
  n ≤ 1,000,000	O(n) or O (logn)
  n ≤ 10,000	O(n2)
  n ≤ 500	O(n3)

Greedy Algorithm

• 탐욕 알고리즘, 선택의 순간에 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 단계적 구분
  1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
  2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
  3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
• 특정한 상황이 아니면 항상 최적의 결과를 보장하지 못함
  • 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
  • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

Implementation(구현)