[ Algorithm - 알고리즘에 대하여(06/30) ]

1. 알고리즘이란?
   • 입력 : 0개 이상의 입력이 존재해야하고, 
   • 출력 : 1개 이상의 출력이 존재해야 한다.
   • 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 하며,
   • 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 하고,
   • 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.
     
     
2. 알고리즘의 표현방법은?
   1. 자연어 (한국어, 영어 ... ) : 변수를 명백히 정의해야 혼동없이 구상할 수 있다.
   2. FlowChart (흐름도) : 시각적으로 흐름이 명백히 보여 좋은 방법이지만, 알고리즘이 복잡할수록 기술이 힘들다.
   3. 유사코드 : 자연어와 컴퓨터언어 사이쯤의 체계적인 언어로, 흔히 알고리즘을 기술하는데 선호되는 표기법이다
   4. 컴퓨터 언어 
      
      
3. 알고리즘의 성능 분석 방법
   • 시간복잡도 : 알고리즘 수행시간
     1. 시간을 측정하는 코드로 확인하면 끝나는게 아닌가? 
        • 보통은, 코드별 시간 측정 함수들을 이용해 시간을 측정할 수 있다.
          but) 실행언어, 실행환경, 여러 실험데이터 등으로 인해 객관적인 시간평가는 불가능하다!
        • 입력의 크기가 커질수록 시간은 입력의 크기 n에 따라 변하게 되는데, 이를 n의 함수로 나타낸 것을 시간복잡도 함수라 하고, T(n)이라 표기한다. 
          but) T(n)은 n이 증가할수록 최고차항의 영향이 가장 크게 나타나므로, 최고차항만으로 시간복잡도를 나타내는 빅오표기법을 주로 사용한다. (여기서는 다루지 않지만, 빅오메가 표기법과 빅세타 표기법도 존재한다)
     2. 그렇다면 빅오표기법이 무엇인가?
        • 정의 : 두개의 함수 f(n), g(n)이 주어졌을 때, 모든 n ≥ n0 에 대하여 | f(n) | ≤ c * | g(n) | 을 만족하는 2개의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다. 
          ==> 정의만으로는 이해가 힘드니 예시를 들어보자
          
          • f(n) = 5 일때, f(n) ≤ 10 * 1 이므로, O(1) 이다.
          • f(n) = 2n+1 일때, f(n) ≤ 3 * n 이므로, O(n) 이다.
          • f(n) = 5 * 2의 n승 + 10 * n제곱 + 100 일때, f(n) ≤  10 * 2의 n승 이므로, O(2의 n승) 이다.
            but) 위의 각 빅오표기법은 정의를 만족하는 가장 작은 빅오표기법을 적은 것이고, 실제로는 많은 값으로 빅오표기법을 이용해 나타낼 수 있다. (상한값이므로) 그래서 이를 보안하고자 등장한 표기법이 빅오메가, 빅세타 표기법이지만, 통상적으로는 빅오표기법으로 나타내되, 최소차수로 상한을 표시하는 편이다.
        •  빅오 표기법에 따른 실행시간 비교
          O(1) < O(log n) < O(n) < O(n * log n) < O(n제곱) < O(2의 n승) < O(n!)    ※ n이 커질수록 만족함
          => T(n)의 상수값이 크고 n이 작은 값이면 반대의 양상을 띌 수 있다.  
          
          위 그림을 보며 이해하길 바란다.
          
          
   • 공간복잡도 : 실행할때 + 실행종료시 필요한 저장공간의 양
     1. 공간복잡도는 어떻게 나타내는가?
        • 흔히, 공간복잡도를 나타낼때는 바이트단위로 하나하나 계산해야할 것 같지만, 실제로는 이도 빅오표기법처럼 나타낸다.
        • 고정공간(알고리즘과 무관) + 가변공간(알고리즘과 관련) => S(P) = c(고정공간은 상수값) + Sp(n)
          => 결론적으로는 알고리즘과 관련된 가변공간만 생각하면 된다!
     2. 알고리즘과 무관 or 관련된 공간은 어떻게 구분할까?
        • 알고리즘과 무관한 공간(고정공간) : 입출력 횟수나 크기에 관계없이 필요한 공간으로, 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수 등이 해당한다.
        • 알고리즘과 관련된 공간(가변공간) : 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간(예를들면 함수내에 선언한 변수들)을 말한다.