[알고리즘 분석] 효율

1. 알고리즘
문제를 해결할 수 있는 잘 정의된 유한 시간 내에 종료되는 계산적인 절차
입력을 받아서 출력으로 전환시켜주는 일련의 계산절차
알고리즘은 프로그램의 엔진에 해당하는 중요한 절차

2. 의사코드 (pseudo-code)
직접 실행할 수 있는 프로그래밍 언어는 아니지만, 거의 실제 프로그램에 가깝게 계산과정을 표현할 수 있는 언어.

3. 흐름도

4. 순차 검색 알고리즘 (Sequential Search)

문제 : 크기가 n인 배열 S에 x가 있는가?
입력 : n, S[n], x
출력 : x가 있다면 위치, 없다면 -1

키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야하는가?
-> 항목의 위치에 따라 다르나, n번
더 빨리 찾을 수 있는 가 ?
-> 다른 정보가 없는 한 불가능

5. 이분 검색 알고리즘 (Binary Search)

문제 : 크기가 n인 정렬된 배열 S에 x가 있는가?
입력 : n,S[n],x
출력 : x가 있다면 위치, 없다면 -1

int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return -1;
    }

이분 검색 알고리즘으로 키를 찾기 위해서는 S에 있는 항목을 몇 개나 검색해야하는 가?
-> while 문 수행시, 검색 대상의 크기가 반으로 줄어들기에 logN+1개만 검색하면 된다.

6. 수학적 귀납법
(1) 귀납출발점 n=0(혹은 1)일 때 주장이 사실임을 보임
(2) 귀납가정 : 어떤 n에 대해서 주장이 사실임을 가정
(3) 귀납절차 : n+1에 대해서 주장이 사실임을 보임

7. 알고리즘의 분석

• 공간복잡도 (space complexity)
  입력 크기에 따라서 작업 공간(메모리)이 얼마나 필요한지를 정하는 절차
• 시간복잡도 (time complexity)
  입력 크기에 따라서 단위 연산이 몇 번 수행되는지 결정하는 절차

8. 분석 방법의 종류

• 모든 경우 분석 (every-case analysis)
  입력 크기에만 종속, 값과는 무관
  입력 값과는 무관하게 결과 값은 항상 일정
  

• 최악의 경우 분석 (worst-case analysis)
  입력 크기와 입력 값에 모두 종속
  단위 연산이 수행되는 횟수가 최대인 경우 선택
  

• 평균의 경우 분석 (average-case analysis)
  입력 크기에 종속
  모든 입력에 대해서 단위연산이 수행되는 기대치(평균)
  각 입력에 대해서 확률 할당 가능
  일반적으로 최악의 경우보다 계산 복잡

• 최선의 경우 분석 (best-case analysis)
  입력 크기와 입력값 모두에 종속
  단위 연산이 수행되는 횟수가 최소인 경우 선택

9. 정확도 분석

정확한 알고리즘 = 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘
정확하지 않은 알고리즘 = 어떤 입력에 대해서 멈추지 않거나, 또는 틀린 답을 출력하면서 멈추는 알고리즘