시간복잡도 (Time Complexity), Big-O
개요 우리가 작성한 코드는 실행시간이 얼마나 걸릴까요? 🤔 컴퓨터는 매우 빠르지만 계산이 복잡하거나 데이터의 양이 많다면 결과를 얻는 시간은 점차 길어질 것입니다. 예를 들면 무작위의 수 5개 중에서 "어떻게 하면 가장 큰 수를 찾을 수 있을까?" 를 고민하는 것을 알고리즘 (algorithm) 이라고 합니다. 알고리즘 : 문제를 해결하기 위한 방법이나 절차 Big-O 표기법 큰 수를 찾는 알고리즘에서 만약 그 수열이 1, 2, 3, 4, 5 와 같다면 가장 처음 만나는 수1을 기록하고 그 다음 수와 비교해가며 큰 수를 만나면 바꿔 기록하는 것이죠. 결국 우리는 수열의 크기인 다섯번을 반복하면 가장 끝에서 만난 5가 가장 큰 수라는 결과를 얻게 됩니다. 다섯번을 반복해 5가 가장 큰 수임을 찾았으니 위 알고리즘을 푸는데 걸린 시간은 5회 라고 볼 수 있습니다. 그것을 시간복잡도 라고 하고 Big-O 표기법 으로 O(5) 라고 합니다. 시간복잡도 : 알로리즘을 수행하는데 걸리는 시간의 양 만약 수열이 5, 4, 3, 2, 1의 순서로 나열되어 있더라도 가장 끝수인 1까지 가야만 첫 수인 5가 가장 크다는 것을 확신 할 수 있으므로 O(5) 입니다. 좀 더 수학적인 표현으로 수열의 크기(n)이 5와 같으므로 O(n) 이라고 할 수 있습니다. 왜 하필 용어가 Max-O도 아니고 Long-O가 아닌지는 너무 고민하지 말고 표준(Standard, 남들이 다 쓰는 말)으로 받아들이면 됩니다. 시간복잡도라는 용어가 조금 이해가 된다면 좀 더 다양한 시간복잡도들을 예시와 함께 살펴보겠습니다. O(1) 시간 복잡도 좀전에 O(n)으로 하자더니 갑자기 O(1)은 뭔가 혼란스럽네요.😩 서로 다릅니다. 예제를 보면서 설명하겠습니다. #include <iostream> using na
