복잡도, 점근적 복잡도, 검색

똑같은 결과라 하더라도 성능이 더 좋은 알고리즘.
즉, 효율적인 알고리즘을 짜는 것이 중요!

복잡도(complexity)

-시간(Time complexity) : 계산량
-공간(Space complexity) : 메모리

계산량이 적은
복잡도가 낮은
효율성이 높은
알고리즘을 짜야 함.

점근적 복잡도

점근적 복잡도 : (데이터의 양) n -> ∞

값이 늘어날 수록 최고차항의 차수가 중요함.
우리는 점근적 복잡도에서 n이 무한대로 커진다는 것을 가정함.
ㄴ> O(n)으로 쓰는 이유.

O(1) : 데이터의 양이 커져도 계산량이 증가하지 않는다. 항상 상수식.

재귀

재귀 = 자기호출(recursion)

재귀적 구조 : 어떤 문제 안에 크기만 다를 뿐 성격이 똑같은 문제가 포함되어 있는 것.
예) factorial, 수열의 점화식

각각의 함수 안에 그 함수 이름이 있어야 함.

$n!$

• $n(n-1)(n-2)…$
  반복적 사고, 반목문적

• $n*(n-1)!$
  순환적, 재귀적, 귀납적 사고

점근적 상한/하한/동일

$O(n)$ - 점근적 상한(빅오)
$Ჲ(n)$ - 점근적 하한(빅오메가)
$Θ(n)$ - 점근적 동일(빅세타)

$O(n)$ : 기껏해야(at most) $g(n)$의 비율로 증가하는 함수
어떤 함수의 최대치, 천장값?
예) $3n^2, 7n^2-3n, nlogn+5n, 3n,….$
$3n$ 같은 경우 $O(n^2)$가 틀리진 않지만 권장x

$Ჲ(n)$ : 적어도(at least) $g(n)$의 비율로 증가하는 함수
어떤 함수의 최소치, 바닥값?
예) $n^2, n^3, 2^n$
$2^n$의 경우 $Ჲ(n^2)$가 틀리지 않지만 권장x

$Θ(n)$ : $g(n)$의 비율로 증가하는 함수
동일한 차수만 포함.
예)$n^2, 2n^2$
다른 차수는 틀림.

검색

계산 기준 -> '비교'
| 최선의 경우 (Best case) | $B(n)$ | $O(1)$ |
| 최악의 경우 (Worst case) | $W(n)$ | $O(n)$ |
| 평균의 경우 (Average case) | $A(n)$ | $O(n)$ |

최악에 초점을 둠.

-순차검색(sequential search) = $O(n)$
n개의 수에 원하는 값이 없다는 것은 n번만에 알 수 있다.

-이진검색(binary search) 실행 방법과 성능에 대한 충분한 이해 필수
전제조건 : 정렬된 데이터
$log_2(n)$

처음과 끝값을 더하고 반으로 나눠 찾는 숫자가 그보다 크거나 작으면 해당 방향만 봐도 된다.

'이진검색알고리즘, binary search algorithm은 단순하지만 강력한 성능을 가지고 있는 알고리즘입니다.

비록, 정렬된 데이터라는 전제 조건이 필요하지만, 전제 조건만 만족한다면 중간 값을 이용하는 방식을 통해, log2의 n번만에 원하는 값의 존재 유무와 위치를 알 수 있습니다.'

T(n) = T(1/2) + 1
.
.
.
.
Log n번 반복