[알고리즘] 2강 - 알고리즘 소개(2)

✅ 1. 알고리즘 분석

(1) 정확성 분석 및 효율성 분석

• 알고리즘을 분석 할 땐 정확성 분석과 효율성 분석을 통해서 분석 할 수 있음.
• ** 하지만, 앞으로 배울 알고리즘은 이미 정확성 분석이 완료 된 정확한 알고리즘 이기에 굳이 다루진 않음. **
• 정리하면, 알고리즘을 분석한다는 것은 대부분 효율성을 분석하는 것이며, 대부분 시간 복잡도를 구하는 것임.

(2) 시간복잡도

• ** 시간복잡도를 구할 때 실제 컴퓨터에서 실행을 시켜 실제 수행시간을 측정할 수는 있지만, 컴퓨터 속도, 구현에 사용된 프로그래밍 언어, 프로그램 작성 방법등 실행 환경에 종속적이므로 일반성이 결여된 방법임. **
• 즉, 반복문을 사용하느냐, 얼마나 효율적인 컴파일러를 수행하느냐에 따라서 달라지기 때문에 측정하기 쉽지 않다 이거임.

• ** 그렇기 때문에 이와 같이 알고리즘의 각 문장들이 수행되는 횟수를 계산해서 다 더한 값을 수행시간으로 보고 있음. **
• 하지만, 수행시간에 영향을 미치는 요인으로 입력 크기, 입력 데이터의 상태가 존재함.
• 입력 크기: 입력된 데이터가 10억개, 1000개 등 다양하기 때문에 문장 연산 횟수로는 정확한 분석이 어려움.
• 입력 데이터의 상태: 입력 데이터의 상태에 따라서 수행 시간이 좋고 나쁨이 정해질 수 도 있음.
• 결국 입력 크기, 입력 데이터의 상태에 따라서 수행시간이 달라질 수 있으므로, 두 가지 상황을 고려해야함.

• 즉, 입력 크기가 10개일 때 10번 실행되는 것과, 10억 개일 때 10억 번 실행되는 것은 같은 알고리즘이라도 실제 걸리는 시간이 완전히 다름.
• 그렇기 때문에 "수행 시간은 입력 크기 n에 따라 변한다" 라는 것을 명시하기 위해 f(n) 이라는 함수 형태로 표현하게 됨.
• 이렇게 해야 데이터가 늘어남에 따라 시간이 얼마나 가파르게 증가하는지(기울기)를 볼 수 있음.
• ** 핵심은 입력 크기 n의 함수와 최악의 수행시간을 기준으로 보는 것임 **
• 최선의 수행시간이 아닌 최악의 수행시간을 기준으로 하는 이유는, 최선은 희망적인 부분만을 보기 때문에 정확한 알고리즘 수행시간은 최악의 수행시간을 기준으로 객관적인 판단을 할 수 있음.

• 이와 같이 각 문장의 연산 횟수를 구한 뒤 입력 크기를 n으로 둔 뒤 수식을 만들면 3n + 5 를 구할 수 있음.
• ** 입력 크기 n을 기준으로 점근성능(입력크기에 대한 기울기)을 구하게 되면, 시간 복잡도를 구할 수 있음. **

---

✅ 2. 점근성능

• 점근성능: 점차적으로 무한에 가까이(근접)가면서 만들어지는 함수의 모습에 따라 결정되는 성능을 의미한다.
• ** 정리하면, 알고리즘에서 성능이란 "얼마나 빨리 끝나는가" 를 의미함. 입력 크기 n 이 무한히 커질 때 함수가 그려내는 곡선의 가파른 정도가 곧 그 알고리즘의 성능 지표가 된다는 의미임. **

(1) 점근성능의 결정 방법

• ** 점근성능은 계수없이 최고차항만을 통해서 점근성능을 표기함 (정확한 값은 아니고 어림값임). **
• 하드웨어 성능이나 프로그래밍 언어에 따라 달라지는 자잘한 수치(계수, 상수)를 다 고려하면 분석이 너무 복잡해짐.
• 또한, 최고차항만으로도 충분히 알고리즘 간의 성능 체급을 한눈에 비교할 수 있음.
• 결과적으로 n의 증가율에 따라서 최고차항의 숫자가 급격하게 커지기 때문이라고 보면됨.
• 완만한 곡선 (log n): 무한으로 가긴 가는데 아주 천천히 올라감 → 매우 좋은 성능
• 직선 (n): 데이터 늘어나는 만큼 정직하게 올라감 → 괜찮은 성능
• 급격한 곡선 (n^2): 조금만 데이터가 늘어도 수직 상승함 → 나쁜 성능

(2) 점근성능의 표기법

• 점근적 상한(Big-O): 해당 알고리즘의 최악의 경우(Worst Case) 를 나타내며, 아무리 나빠도 이 정도 시간 안에 끝난다라는 상한선을 의미하는 개념임.
• 쉽게말해, O(n^2) 인 경우 해당 알고리즘이 아무리 상황이 나빠져도 n^2의 속도는 절대 넘지 않는다는걸 보장하는 것임.
• f(n): 실제 함수를 의미하며, 쉽게말해 알고리즘이 실제로 실행될 때 걸리는 실제 수행 시간을 의미함.
• cg(n): 기준선이 되며, 해당 함수는 상수 c를 곱해서 아무리 최악의 상황이라도 이 선은 넘지 않는다는 가이드 라인을 제공함.
• ** 해당 cg(n) 은 쉽게말해, 실제 알고리즘의 연산 횟수를 더한 결과값에 최고차항을 기준을 특정 상수를 곱했을 때 결과를 기준선으로 보는 것임. **
• f(n) <= c*g(n) 인 경우, f(n)=O(g(n)) 이런식으로 표기가 되며, 해당 O(g(n)) 은 기준선을 정해놓아 상한을 걸어 최소한 이 정도 시간 안에는 끝난다는 것을 표기한 것임.
• 예시를 들면, f(n) = 3n^2 + 2n + 3 (연산 횟수 더한 결과) 인 경우, 최고 차항인 n^2 를 기준선으로 만들기 때문에 f(n) = O(g(n)) 은 f(n) = O(n^2) 으로 되는 것임.
• ** 즉, 해당 함수 f(n) 은 O(n^2) 인 점근적 상한인 적어도 n^2 의 수행 시간 안에는 끝난다 라는 것을 보장하는 것임. **

 

• 빅오(O) 표기법은 실제 함수의 증가율에 상수배를 한 특정 함수 중 가장 낮은 함수 즉, 실제 함수의 증가량 바로 위에 존재하는 함수를 통해 빅오( 이 범위는 넘을 수 없으므로, 이 정도의 성능을 냄 ) 를 통해서 시간 복잡도를 표기할 수 있음.
• 즉, 실제 함수의 증가량보다 높으면 된다는 의미지만, 그 중 가장 낮은 함수를 기준으로 보겠다는 의미임.
• 또한, 특정 상수배를 한 값에 따라서 현재 함수의 최고차항의 상수들을 넘어설 수 있고, 상수는 증가율에 미미하게 작용하기 때문에 생략을 함. 결론은 n^3 에 특정 상수배는 생략함.
• 결론은 최고차항의 값이 빅오로 표기가 될 수 있음.
• 빅오메가 또한, 실제 함수 증가율보다 반드시 낮아야 하지만, 낮은 함수 중 가장 차수가 높은 함수를 기준으로 사용하게 됨.
• ** 결론은, 빅오, 빅오메가, 빅세타 모두 n^3 이라는 시간 복잡도를 가질 수 있게 됨. **
• 실질적으로 최고차항만을 기준으로 보면 되지만, 수학적인 증명을 하기 위해서 이러한 개념이 존재한다는 의미임.

(3) 점근성능 - 표기 간 연산 시간의 크기 관계

• 결론은 위와같이 최고차항의 값을 점근성능 표기법으로 O(N) 형식과 같이 표현 할 수 있음.
• 또한, 위와 같이 상수 시간이 가장 효율적이며 지수 시간이 가장 비효율적으로 나타낼 수 있음.

(4) 점근성능 - 빅오 함수에 따른 연산 시간의 증가 추세

• 결론은 위와 같은 증가 추세에 따라서 어떤 알고리즘의 시간복잡도가 효율적인지를 알 수 있음.

(5) 알고리즘 - 시간 복잡도 구하기

• 기본 연산의 수행 횟수 합인 특정 f(n) 함수를 구한 뒤, O(g(n)) 을 만족하는 최소 차수의 함수 g(n) 을 찾는 것임.
• 쉽게말해, 점근적상한 중에 가장 작은 값을 구하는데, 상수는 생략한다는 의미이며, 결론은 최고차수가 되는 것임.

• 즉, 결론은 굳이 복잡한 수학적 계산을 안하고도 단순하게 최고차수만을 구한 뒤 표기하면 되는 것임.

---

✅ 3. 순환 알고리즘

(1) 순환 알고리즘의 성능

• 일반적인 반복문 알고리즘은 루프가 돌아가는 횟수를 세는 것만으로도 복잡한 계산이 가능함.
• 하지만, 자기 자신을 다시 호출하는 순환 알고리즘은 그 구조가 층층이 쌓여 있기 때문에 직관적으로 파악하기 어려움.
• ** 그렇기 때문에 위와 같은 점화식을 통해서 분석할 수 있음. **
• ** 결론은 점화식을 세운 뒤에는 이를 일반항으로 풀어서 빅오 표기법으로 변환을 해줘야 함. **
• 예시 코드를 풀면, T(n) 은 해당 알고리즘 수행 시간을 의미하며, 이진 탐색 알고리즘의 총 데이터는 n 개 이므로, 왼쪽 절반과 오른쪽 절반 한 번 접근 할 때는 절반만 수행하기 때문에 T(n/2) 가 될 수 있으며, 상수 시간 O(1) 을 더하면 한 번 수행임.
• 이후, 해당 점화식을 빅오 표기법으로 변환해야 하므로, 식에 대한 답을 구해야함.

[ 초기 설정 ]

• T(n): 데이터가 n개일 때 걸리는 전체 시간을 의미함.
• T(n/2): 이진 탐색은 한 번 확인하면 탐색 범위가 절반(n/2)으로 줄어듬. 즉, 절반짜리 문제를 푸는 시간을 의미함.
• c2: 중앙값을 확인하고 비교하는 데 드는 상수 시간임. 한 번 나눌 때마다 이만큼의 시간이 추가 됨.
• T(1) = c1: 데이터가 딱 1개 남았을 때 걸리는 시간(기본 케이스)임.
• 해당 이진 탐색은 중간 연산으로 중간 위치 mid 를 계산 또는 비교 하는 연산을 하는데, 이것을 상수 시간(c2) 으로 갖음.

[ 반복 전개 (치환 과정) ]

• 이미지 중간의 줄들은 식을 계속 확장하며 규칙을 찾는 과정임.
• 1단계: T(n) = T(n/2) + c2
• 2단계: T(n/2) 자리에 다시 식을 대입하면 T(n/4) + c2가 되므로, 전체 식은 T(n/4) + 2c2가 됨.
• 3단계: 한 번 더 하면 T(n/8) + 3c2 가됨.
• 즉, 결과는 분모가 2^k으로 커질 때, 뒤에 더해지는 상수는 k * c2가 됨.
• ** 쉽게말해, T(n/8) + c2 + c2 + c2 는 결국 T(n/2^3) + 3c2 로 치환이 가능함. **
• 또한, T(n/2^3) + 3c2 이 결과는 T(n/2^k - 1) + (k - 1)c2 로 치환이 가능해짐. ( 계속해서 늘어날 수 있기 때문 )

[ 종료 조건 및 k값 찾기 ]

• 재귀 호출은 위와 같이 데이터가 1개가 될 때인 T(1) 일 때 종료가 되게 됨.
• 즉, 수학적인 식을 보면 n/2^k = 1 이 되는 지점을 찾는 과정이라고 보면 됨.
• ** 양변에 2^k 을 곱하면 n = 2^k 이가 될 수 있으며, 여기서 k를 구하기 위해 로그를 취하면 k = log2n이 되는 것임. **
• 결론은 세타(log2n) 이 되는 것이며, 굳이 세타를 쓴 이유는 단순히 log2n 시간 근처에서 끝난다를 표기하기 위함임.

(2) 기본 점화식과 폐쇄형

• 점화식: 다음 단계는 이전 단계에 뭘 더해야 하는지 길을 알려주는 식임.
• 폐쇄형: 결과값은 이거다 라는 딱 정해서 한 번에 계산이 되는 식임.
• 즉, 점화식처럼 무한히 반복(재귀)될 가능성이 열려 있는게 아닌, 우리가 아는 기본적인 연산(더하기, 뺴기, 곱하기, 나누기, 로그, 지수 등)들을 유한하게 조합해서 딱 끝을 맺었다는 의미에서 폐쇄형이라고 부름.
• ** 쉽게 정리하면, 점화식을 기반으로 폐쇄형으로 유도하면서 치환하는 과정을 통해 성능에 대한 수식을 정리하는 것임. **
• 대표적인 알고리즘과 점화식이며, 점근성능 표기법임.
• 결론은 순환 알고리즘인 재귀 함수의 성능을 구하기 위해서 점화식을 이용하는 방법이라고 보면 됨.
• ** 2, 3, 6번은 외워야함. ( 앞으로 배울 알고리즘임. ) **

(3) 효율적인 알고리즘의 중요성

• ** 입력 크기에 대한 수행시간 차이가 확연하기 때문에, 효율적인 알고리즘을 설계하는 것은 필수 덕목이라고 보면 됨. **