알고리즘 (Algorithms)
: An algorithm is a step-by-step procedure to solve a problem
알고리즘의 전반적인 개념에 대해 알아보겠다! 😆
알고리즘의 표기
- 자연어: 한글 또는 영어
- 프로그래밍 언어: C, C++, Java, ML 등
- 의사코드: 설계자가 알고리즘 로직에 집중할 수 있도록 알고리즘을 묘사하는 정형화된 언어이다.
* C++은 반드시 배열의 인덱스가 0부터 시작하지만 의소코드는 임의의 값을 사용 가능하다.
* 그리고 의사코드는 참조 파라미터를 사용하여 프로시저의 결과값을 전달한다.
Sequential Search (순차 검색)
f(n) = 1회 ⇒ best case
f(n) = n회 ⇒ worst case (비교를 가장 많이 함)
💡 T(n): 시간복잡도, W(n): 최악의 경우, B(n): 최고의 경우
* 앞으로 식은 위와 같이 나타내겠다! 😍
Binary Search Algorithm (이분 탐색)
B(n) = 1회 ⇒ 최고의 경우는 쉽게 구할 수 있지만
W(n) = ?회 ⇒ 최악의 경우는 쉽게 구하지 못할 것이다.
그래서 아래와 같이 예시를 통해 점화식을 구해봐야 한다.
1 2 3 4 5 6 7 8
W(8) = 4회
W(16) = ?회
W(n) =?
n = 2^k
W(2^k) = k + 1
Lgn =Lg2^k = k
W(n) = |Lgn| + 1
Fibonacci Sequence (피보나찌)
T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2) + 1
T(n) = T(n-1) + T(n-2) + 1
따라서 T(n) > 2^(2/n)
최소한의 하한선을 구하는 것
** 특징: 꼬리재귀 **
항상 함수의 꼬리부분(마지막)에서 실행되는데, return되기 전에 값이 정해지며 호출당한 함수의 결과값이 → 호출하는 함수의 결과값으로 반환된다.
입력값에 따라 달라지는 게 없음
즉, best case와 worst case가 없음
따라서 every case
차수 (Order)
