반응형
목차
시간 복잡도 O(n^2)이란?(Time Complexity)
O(n^2)이란?
O(n²)는 입력 크기에 따라 알고리즘 실행 시간이 제곱으로 증가한다는 것을 의미합니다. 예를 들어, 입력 크기가 두 배가 되면 실행 시간은 네 배로 증가합니다. 이런 알고리즘은 큰 입력에 대해 느려질 수 있으며, 더 효율적인 알고리즘에 비해 성능이 떨어질 수 있습니다.
O(n^2) 계산 방법
O(n²) 시간 복잡도를 nC2와 관련하여 설명하자면, nC2는 n개의 항목 중에서 2개를 고르는 조합의 수를 나타냅니다.
이는 (n*(n-1))/2로 계산되며, 이 식에서 가장 큰 영향을 미치는 항은 n²입니다. 따라서, nC2의 성장률이 n²에 비례한다고 볼 수 있습니다. 배열에서 모든 쌍의 요소를 비교하여 중복을 확인하는 알고리즘이 있다면, 이 알고리즘은 nC2번 비교를 수행하게 되므로, 시간 복잡도는 O(n²)입니다.
O(n^2) 예제 실습
예를 들어, n명의 사람들 중에서 2명을 선택하여 팀을 만드는 모든 경우의 수를 찾고 싶다고 가정해 봅시다. 이 경우, 각 사람을 한 번씩 다른 모든 사람과 짝지어 보면서 팀을 만들 수 있습니다. 이러한 과정은 n*(n-1)/2번 반복되므로, 이 알고리즘의 시간 복잡도는 O(n^2)입니다. 이는 큰 n 값에 대해 매우 많은 연산을 필요로 하므로, 데이터가 많을 때는 효율적인 방법을 고려해야 합니다.
반응형