시간 복잡도
-
효율적인 알고리즘을 구현한다는 것은 시간 복잡도를 효율적으로 작성했다는 것
-
입력값이 커짐에 따라 증가하는 시간의 비율(시간 복잡도)을 최소화한 알고리즘
-
시간 복잡도는 주로 빅-오 표기법으로 표현합니다.
Big-O 표기법
종류 : O(1), O(N), O(logN), O(n^2), O(2^n)
1. O(1)
-
constant complexity
-
입력값의 크기와 관계없이, 즉시 출력값을 얻어내는 알고리즘.
2. O(N)
-
linear complexity
-
입력값이 증가함에 따라 출력값을 얻어내는 시간 또한 증가하는 알고리즘.
-
입력이 1일때 1초 걸린다고 가정한다 치면, 입력이 100이 되면 100초 걸린다.
-
for문, 배열을 예로 들자면 배열 전체를 모두 탐색해야 할 경우
3. O(logN)
-
logarithmic complexity
-
O(1) 다음으로 빠르다.
-
쉽게 예로 들어 탐색을 하는 알고리즘이라면 중간값부터 탐색을 시작해 절반씩 범위를 줄여가는 알고리즘.
-
입력값이 커지면 커질수록 시간은 줄어든다.
4. O(n^2)
-
quadratic complexity
-
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다.
-
쉽게 예를 들면 이중 for문을 쓴 경우, 1차 for문의 모든 경우에 대해서 2차 for문을 다 수행해야 한다.
5. O(2^n)
-
expotential complexity
-
가장 느린 시간 복잡도
-
대표적인 예로 피보나치 수열 구하는 알고리즘
느낀점 && 미비한 점
위의 시간 복잡도 외에 알고리즘을 푸는 방식에 대하여 여러 가지를 배웠지만 아직 알고리즘 문제만 보면 해당 문제만 보이지 여러가지 기존 방식 혹은 시간 복잡도가 연관지어 생각되어 지지 않는다. 당장 어떻게 해결할수는 없다고 생각한다. 많이 보고 많이 푸는 수밖에 없다고 생각한다.
