시간복잡도에 관하여
2019.05.11 Sat 14:15
이번 일지를 기준으로 가끔가면서 기억에 남는 일이 있으면 차례대로 써서 기록을 남겨보기로 했습니다.
이런식으로 일지를 써보는 건 처음이라 조금 걱정되기도 하네요.
우선 한가지 반성하면서 넘어가 볼 일을 써볼까합니다.
오늘 공주대학교 정보보호영재원 수업은 python과 알고리즘이었습니다.
이곳에서 받은 강의 자료에서 제가 한 가지 잊고서 공부하지 않고 있던 것을 발견할 수 있었습니다.
바로 시간복잡도입니다.
시간복잡도의 개념만 알고 나중에 알아둬야지 하고 넘기다가 지금까지 공부를 안해놓은 자신을 발견할 수 있었습니다.
그래서 오늘의 일지는 오늘 공부한 시간복잡도에 대해서 남겨보려고 합니다.
| big-O | Name |
| 1 | Constant |
| log n | Logarithmic |
| n | Linear |
| n log n | Log Linear |
| n^2 | Quadratic |
| n^3 | Cubic |
| 2^n | Exponential |
- O(1)
- Constant, 즉 1이 의미하는 바는 상수 시간을 의미합니다.
- 입력되는 n이 주어질 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
- O(log n)
- Logarithmic, 즉 고정된 밑이 몇 번 제곱되는지에 대한 시간을 의미합니다.
- 밑을 2라고 생각하였을 때, n의 입력값이 16이면 알고리즘 수행 시간은 4가 됩니다.
- 따라서 데이터 양이 많아져도, 그에 비한 시간은 조금씩 늘어납니다.
- Binary Search, 즉 이진 탐색의 코드에서 주로 나타나는 시간복잡도입니다.
- O(n)
- Linear, 즉 선형이므로 데이터 양에 따라서 시간이 정비례합니다.
- linear search, for문을 통한 탐색의 코드에서 주로 나타나는 시간복잡도입니다.
- O(n log n)
- log linear, 즉 데이터 양이 n배 많아지면, 실행 시간은 n배보다 조금 더 많아지는데, 정비례는 하지 않는다.
- n이 두배로 늘어나면 실행 시간은 2배보다 약간 더 많이 늘어난다.
- Quick sort, Merge sort 방식의 정렬 알고리즘에서 주로 나타나는 시간복잡도입니다.
- O(n^2)
- Quadratic, 즉 데이터 양에 따라 걸리는 시간은 제곱에 비례합니다.
- 제곱하는 만큼 n값이 커질수록 걸리는 시간이 비효율적으로 늘어나게됩니다.
- 이 유형은 이중루프내에서 입력 자료를 처리하는 경우 나타납니다.
- 2중 for 문을 사용하는 bubble sort, insertion sort와 같은 정렬 알고리즘에서 주로 나타나는 시간복잡도입니다.
그 외에도 n!와 같이 팩토리얼 형식의 시간복잡도도 쓰이지만, 여기서는 언급하지 않고 넘어가겠습니다.
각각의 시간복잡도들의 성능만 따져본다면
O(1)>O(log n)>O(n)>O(n log n)>O(n^2)>O(n!)
가 됩니다.
정말 시간복잡도도 제대로 파악할 줄 몰라왔으면서 지금까지 잘도 시간초과가 나지 않도록 코딩해왔다는 생각이 들었습니다.
사실 이론으로 설명해놓은 이 정리보다는 직접 예시 코드를 보고 이해하니 금방 이해할 수 있었습니다.
한 번만 읽어봐도 코딩하면서 머리를 좀더 효율적이게 굴리며 코딩해올 수 있었을 간단한 내용들인데, 그 간단하다고 말하는 내용을 미뤄두면서 안해왔던 저를 반성하는 시간이 된 것 같습니다.
음, 첫 번째로 쓰는 일지..라 해야할까 일기에 더 가까운 것 같군요.
처음 쓰는 방식이라 두서없이 내용이 길어진 것 같습니다.
다음번에는 좀 더 정리해가며 일지를 써야될 것 같네요.