시간복잡도에 대해 알아보자 (빅오표기법, 빅오메가, 빅세타)
시간복잡도에 대해 알아보자 (빅오표기법, 빅오메가, 빅세타) — #시간복잡도 #빅오표기법 AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다. 효율적...
#시간복잡도 #빅오표기법
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다.
효율적인 코드 작성
하나의 목적을 달성하기 위해서 각 사람마다 코드를 작성하는 방식이 모두 다릅니다. 사람마다 생각이 다 다르기도 하며, 목적을 달성하기 위한 수단이 다양한 경우가 많습니다.
예를들어 부산에서 서울까지 이동하는것이 목적인 경우를 생각해봅시다. 김해공항으로 가서 비행기 타고 날아가는 방법이 있고, 자동차를 타고 고속도로를 밟으며 가는 방법도 있습니다. 어떤이는 중간에 있는 도시들을 하나 하나 탐방하면서 가고 싶어할 수도 있습니다. 모두 같은 결과(서울 도착)를 가지지만, 결과를 도출하는데 걸리는 시간은 저마다 다 다릅니다.
이와 마찬가지로 같은 결과를 낼 수 있는 코드작성 방식은 매우 다양하며, 각 코드마다 실행속도의 차이를 보입니다. 현실세계에서도 항상 가장 효율적인 방법을 찾으며 살아가듯이, 우리는 코드를 작성할 때 가장 빠르게 결과를 얻을 수 있는 방법을 찾아내야합니다.
우리는 이를 시간복잡도를 개선한다고 말합니다.
시간복잡도
시간복잡도
결론적으로 시간복잡도는 "이 코드가 얼마나 빠르게 작동하는데?"에 초점을 두고 있습니다. 코드의 길이가 길어지면, 그만큼 연산하는 양도 많아지는게 당연합니다. 하지만 코드가 길어지더라도 연산하는 양을 최대한 줄이는 방향으로 코드를 작성하는 것이 좋습니다.
시간복잡도가 낮다는 것은, 결과를 얻는데 까지 걸리는 시간이 매우 빠르다는 의미이며, 시간복잡도가 높다는 의미는 연산해야할 양이 많아져 결과를 얻는데 까지 걸리는 시간이 길다는 의미가 됩니다.
표기법
표기법은 "실제 이런 속도를 가진다" 보다는 "이런 속도정도를 가지겠구나"를 짐작하는 표기방법입니다. 작성한 코드는 언제든지 상황에 따라 다른 속도를 보이기 때문에 짐작해서 표기할 수 밖에 없습니다. (물론 실제속도를 구할수도 있겠지만요) 표기법은 현업에서 코드를 작성후에 "제가 작성한 코드가 이정도 실행속도를 가질것 같습니다"를 말하는 소통의 언어로 보시면 됩니다.
빅오메가(Ω)
어떤 알고리즘을 빅오메가로 표기했다는 것에 대해 정확한 의미를 알고 있는것이 좋습니다. 에시를 통해 빅오메가가 무엇을 뜻하는지 알려드리겠습니다.
| Ω(n) |
|---|
어떤 알고리즘의 시간복잡도를 Ω(n)으로 표기했다고 가정해 봅시다. 이때 그 알고리즘의 속도는 다음과 같이 해석될 수 있습니다. "이 알고리즘은 n과 같거나 n보다 느리겠구나"
즉 Ω로 표현한다는 것은 해당 표기법보다 느린것을 짐작하게 만드는 표기법입니다. 같은 맥락으로 모든 알고리즘 코드는 Ω(1)로 표현이 가능합니다. 모든 알고리즘은 Ω(1)과 비슷하거나 느린 실행속도를 가지기 때문입니다.
빅오(O)
빅오는 빅오메가와 반대라고 이해하시면 됩니다. 이번에도 예시를 가져왔습니다.
| O(n²) |
|---|
어떤 알고리즘이 O(n²)로 표기되어 있다면 다음과 같은 의미를 같습니다. "아 이 알고리즘은 거의 n²속도이거나 n²보다는 빠르겠구나"
O로 표기하는 것은 해당 표기법보다는 빠르겠지를 짐작가능하게 하는 코드입니다.
빅세타(θ)
빅세타는 자주등장하지 않는 케이스입니다. 왜나하면 빅세타로 표기가능한 알고리즘이 실제로는 흔하지 않기 때문입니다.
| θ(n²) |
|---|
위 코드는 알고리즘이 n²의 속도로 증명된 경우로 볼 수 있습니다. 거의 모든 경우에서 n²이 속도를 가진다는 의미입니다.
θ를 사용하려면 O와 Ω가 동일한 속도를 나타낼 수 있어야합니다.
O(1)
O(1)
O(1)의 경우는 입력값이 증가해도 즉시출력이 가능합니다.
대표적인 예시로는 자료구조 배열에서 index로 접근하는 경우가 있습니다.
| arr = \[1, 2, 3, 4\]arr\[1\] = 1 |
|---|
배열의 요소들은 index의 값에 상관없이 즉시 출력이 가능하기 때문에 배열의 0번째 요소든 100,000번째 요소든 똑같은 속도로 출력이 가능합니다.
자세한건 자료구조를 참고하세요!(업데이트 예정)
O(N)
O(N) - 선형복잡도
입력값이 증가함에 따라 연산속도 역시 선형적으로 증가하는 경우입니다.
| n = int(input('갯수 입력'))list = \[0\] \ nprint(list)for i in* range(len(list)): print(i) |
|---|
간단하게 예시 코드를 작성해 보았습니다. n의 입력값에 따라 list안의 0의 갯수가 달라지며 반복문의 i출력이 n만큼 늘어나게 됩니다.
O(logN)
O(logN) - 로그복잡도
O(1)다음으로 가장 빠른 시간 복잡도입니다. 이진 탐색 트리의 시간복잡도로 잘 알려져 있습니다. 자료구조를 아직 모르시는 분들을 위해 간단하게 설명하자면 업다운 게임을 생각해보시면 됩니다.
업다운 게임
1~100까지 임의의 숫자를 맞추는 게임입니다. 정해진 숫자가 제시한 숫자보다 클경우 up을 작을경우 down이라는 힌트를 얻을 수 잇습니다.
보통 이때 남아있는 절반값을 기준으로 제거해 나갑니다.
1~100 -> 50
1~50 or 51~100 -> 25, 75
1~25 or 26~50 or 51~75 or 76~100 -> 13 or 36 or ....
O(N²)
O(N²)- 2차 복잡도
입력값이 증가함에 따라 연산해야할 값이 제곱으로 늘어남
| n = int(input('갯수 입력'))list = \[0\] \ nprint(list)for i in range(len(list)): for j in* range(len(list)): print(i, j) |
|---|
가장 이해하기 편한 예시로 이중 for문을 생각해보시면 될 것 같습니다. 위 코드에서 n 값이 주어지면 i가 n번 연산되고 j가 n번 연산이 됩니다. 해당 코드의 시간 복잡도는 n x n으로 n²이됩니다.