알고리즘(Algorithm)?
우리는 컴퓨터로 많은 문제를 해결합니다.
여기서 문제를 해결한다는 의미는 우리가 아는 흔한 수학 문제일 수도 있고 실생활에 필요한 요구사항일 수도 있습니다.
하지만 컴퓨터는 사람처럼 똑똑하지 않아서 시키는 일만 수행합니다.
그렇기 때문에 컴퓨터로 사람이 요구 하는 문제를 해결하기 위해서는 그 문제에 대한 해결 방법을 함께 제시해줘야 합니다.
그것을 알고리즘이라고 부릅니다. 더불어 한 가지 문제에대한 여러 가지 해결 방법이 있을 수 있고,
이러한 상황 속에서 성능 분석을 통해서 가장 좋은 알고리즘을 선택해야 합니다.
공간 복잡도(Space Complexity)와 시간 복잡도(Time Complexity)
컴퓨터에게 명령을 내리는 알고리즘의 성능의 척도에는 공간 복잡도와 시간 복잡도가 있습니다.
공간 복잡도는 해당 알고리즘을 수행하는 데 있어서 필요한 메모리 양이며,
시간 복잡도는 해당 알고리즘을 수행하는 데 필요한 시간입니다.
그리고 이러한 복잡도를 우리는 세 가지 점근적 표기법을 활용해 나타냅니다.
점근적 표기법
점근적 표기법은 아래와 같이 세 가지로 표시하며 뜻은 다음과 같습니다.
점근적 상한을 나타내며, "아무리 심해야 이 정도다." 라는 의미입니다. (최악의 경우)
점근적 하한을 나타내며, "최소한 이 정도다" 라는 의미입니다.(최선의 경우)
점근적 하한을 나타내며, "대략 이 정도다" 라는 의미입니다.(평균적인 경우)
이러한 표기법들은 보통 문제 해결에 대한 입력 n에 대해서 표기합니다.
앞으로 다양한 알고리즘을 소개할 때, 보통 Oh 표기법을 많이 활용할 것 입니다.
왜냐하면 많은 시스템에서 성능을 보장하기 위해서는 최악의 경우를 고려하는 것이 올바르기 때문입니다.
이번 포스팅은 여기까지 진행하도록 하겠습니다!
추가적으로 설명이 필요한 부분이 있다면, 언급해주시고 계속 수정하도록 할게요
그리고 다음 포스팅에서는 
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] - 퀵 정렬(Quick sort) #6 (0) | 2019.01.31 |
|---|---|
| [알고리즘] - 선택 정렬(Selection sort) #5 (0) | 2019.01.16 |
| [알고리즘] - 삽입 정렬(Insertion sort) #4 (3) | 2019.01.15 |
| [알고리즘] - 버블 정렬(Bubble Sort) #3 (1) | 2019.01.10 |
| [알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2 (5) | 2019.01.09 |