[알고리즘] 알고리즘과 효율, 차수, 분석

💡알고리즘 이란?

- 주어진 문제를 논리적으로 해결하는 과정

- 분석을 통해 효율성 파악, 효율성을 정량화

- 알고리즘은 프로그래밍 언어에 독립적 (언어에 따라 구현 문법은 좀 다르겠지만 원리는 동일하게 동작)

 

✔알고리즘의 따라 효율이 달라질 수 있다?

 

예1) 순차검색 vs 이진검색

- 순차검색은 처음부터 찾고자 하는 원소가 나올 때까지 진행 -> 원소가 가장 마지막에 있으면 시간 오래 걸림

- 이진검색은 중간에 있는 원소부터 시작해 찾고자 하는 원소보다 큰지 작은지에 따라 오,왼으로 이동해 다시 중간 원소와 비교 -> 비교적 시간 단축

 

예2) 피보나치항 계산의 재귀 vs 반복

- 반복문을 사용해 계산된 항의 개수는 n+1 

- 재귀함수를  사용해 계산된 항의 개수는 2^(n/2) (단, n>=2)

 ex) T(2) = T(1) + T(0) +1 = 3 > 2^1=2  

      T(3) = T(2) + T(1) + 1 = T(1) + T(0) +1 + T(1) + 1 = 5 > 2^(3/2)

      T(4) = T(3) + T(2) + 1 = T(1) + T(0) +1 + T(1) + 1 + T(1) + T(0) +1 + 1=  9 > 2^2=8

 

      *사용되는 항의 개수는 자기 자신도 포함

      * T(0), T(1) 계산해 사용되는 항의 개수는 자기 자신 1개 뿐이다. 

int fib(int n){
	if(n<=1) return 1;
	else return fib(n-1)+fib(n-2);
}

재귀함수를 사용하면 계속 해서 T(0), T(1)이 나올 때가지 반복해서 함수를 호출하기 때문에 효율성이 떨어진다

(함수의 중복 호출)

 

귀납적 증명: 

 

 

💡복잡도 분석

   ✔ 시간복잡도 분석(Time complexity): 입력크기를 기준으로 단위연산을 몇 번 실행하는지 구하는 것 

       1) 일정 시간 복잡도 분석 - 입력크기에만 종속, 입력값과는 무관하게 복잡도는 일정 ex)배열의 원소 모두 더하기

       2) 평균 시간 복잡도 분석, A(n) - 입력크기 n에 대해 실행할 단위연산의 평균 회수(기대치)

          * 배열에 찾고자 하는 원소가 있는지 없는지 확률에 따라 달라진다. 

            A(n) = n(1-p/2) + p/2  (p는 배열에 있을 확률)

       3) 최선 시간 복잡도 분석, B(n) - 입력크기 n에 대해 실행할 단위연산의 최소 횟수 

       4) 최악 시간 복잡도 분석, W(n) - 입력크기 n에 대해 실행할 단위연산의 최대 횟수

  ✔ 차수의 특성

       - 알고리즘이 얼마나 복잡한지를 정랼적으로 다루기 위한 개념

       - 입력크기가 매우 큰 경우, 대체로 차수에 따라 복잡도가 결정됨

  ✔ 복잡도 카테고리

     로그 -> 1차- > n*로그 -> 2차 -> 3차 -> 지수 -> 팩토리얼

 

💡Big O 표기법

💡Omega 표기법

💡Small o(o)표기법

 

💡극한을 사용하여 차수 결정하기