Algorithm

1)의미

:문제를 해결하는 최선의 선택

효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘이다.

2)Time Complexity

:시간의 복잡도

-표기법

1)Big-O(빅-오) :최악의 경우에 대하여 나타내는 방법
2)Big-Ω(빅-오메가):최선의 경우에 대하여 나타내는 방법
3)Big-θ(빅-세타):평균의 경우에 대하여 나타내는 방법
최악의 경우도 고려하여 대비하는 것이 일반적이므로 다른표기법보다 Big-O를 많이 사용한다.

-O(1)

:constant complexity
입력값이 중가하더라도 시간이 늘지 않는다. 그래프로 생각했을 때 상수함수와 같다. x값이 어떤값이 들어오든 일정한 값을 유지한다.

-O(n)

:linear complexity
입력값에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다. 입력값을 n배 만큼 늘렸을 때 시간도 n배만큼 늘어난다.

-O(logn)

:logarithmic complexity
O(1) 다음으로 빠른 시간 복잡도를 가진다. BST(binary sreach tree)에서 원하는 값을 탐색할 때 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는 것과 같다.

-O(n^2)

:quadratic complexity
입력값에 따라 n의 제곱수의 비율로 증가하는 것을 의미한다.예를들어 이중 for문과 같다.
(n^3,n^4 등등 다 n^2으로 표기한다)

-O(2^n)

:exponential complexity
Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.예를들어 recursive한 피보나치수열과 같다. 입력값이 늘때마다 엄청큰 시간이 걸린다.

3)알고리즘 해결하는 방법

-문제를 순서대로 풀 수 있어야 한다
-문제의 시작과 끝을 알아야 한다
-문제의 크기를 알아야 한다(대부분은 입력의 크기)
-문제의 크기에 따라서 시간복잡도를 고려해야한다.(오늘날 상대적으로 공간복잡도는 크게 중요하지 않다)

4)알고리즘 풀기 tip

코딩테스트를 풀 때 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측해볼 수 있다. n이 1.000.000보다 작은 수 일때 O(n) O(nlogn)의 시간복잡도를 가지고 에측할 수있다 . n^2은 너무 커진다.

데이터 크기 제한 예상되는시간 복잡도
n ≤ 1,000,000 O(n) or O (logn)
n ≤ 10,000 O(n2)
n ≤ 500 O(n3)