[알고리즘] 시간복잡도 알고리즘

1. 시간복잡도의 O(n)과 O(nlogn)의 차이

O(n)

• 의미: 데이터의 크기 nnn에 비례하여 연산 횟수가 증가합니다. 데이터가 nnn만큼 커지면 수행 시간도 비슷하게 nnn배로 증가합니다.
• 특징:
  • 비교적 빠릅니다.
  • 선형적으로 연산을 수행하기 때문에 대규모 데이터에도 적합합니다.
  • 예: 투포인터 알고리즘, 단일 반복문을 사용하는 탐색 문제.

---

O(nlogn)

• 의미: 데이터 크기 nnn에 로그 크기를 곱한 만큼 연산 횟수가 증가합니다. 이는 정렬 알고리즘과 같은 문제에서 자주 나타납니다.
• 특징:
  • nnn이 작을 때는 O(n)보다 큰 차이가 나지 않지만, nnn이 커질수록 느려집니다.
  • log⁡n\log nlogn은 느리게 증가하기 때문에 큰 nnn에서도 실용적일 수 있습니다.
  • 예: 퀵소트, 병합 정렬 등 효율적인 정렬 알고리즘.

---

2. 주의해야 할 점

O(n)의 알고리즘을 사용할 때

1. 단일 반복문에서 실행:
   • O(n)은 모든 데이터를 한 번씩 살펴보는 연산이므로, 불필요하게 중복된 연산이 없어야 합니다.
2. 데이터 크기가 매우 크더라도 적합:
   • 데이터 크기가 nnn에 비례한 연산량이므로, 대규모 입력에도 실용적입니다.

---

O(nlogn)의 알고리즘을 사용할 때

1. 데이터 정렬이 필요한 경우:
   • 정렬을 미리 수행해야 투포인터처럼 효율적인 알고리즘을 사용할 수 있습니다.
2. 데이터 크기에 유의:
   • nnn이 매우 클 경우 nlog⁡nn \log nnlogn은 O(n)보다 연산량이 많아질 수 있습니다.
3. 정렬 비용과 이후 연산의 효율성 비교:
   • 정렬 이후 O(n)으로 해결 가능한 문제라면 전체적으로 O(nlogn)만큼의 효율성을 가질 수 있습니다.

---

3. 어떤 상황에서 어떤 시간복잡도를 선택해야 하는가?

(1) N이 큰 경우 (예: 1<N<10,000,0001 < N < 10,000,0001<N<10,000,000)

• 이 경우 nnn이 매우 크므로, O(nlogn)보다 O(n)을 사용하는 것이 바람직합니다.
• 이유:
  • nnn이 클수록 nlog⁡nn \log nnlogn의 시간복잡도가 O(n)보다 훨씬 느려집니다.
  • 투포인터와 같은 O(n) 알고리즘은 정렬 없이 바로 데이터를 처리하므로 더 효율적입니다.

(2) N이 비교적 작은 경우 (예: 1<N<15,0001 < N < 15,0001<N<15,000)

• 이 경우 O(nlogn)으로 정렬 후 O(n) 알고리즘을 사용하는 것이 가능합니다.
• 이유:
  • nnn이 작을 때는 log⁡n\log nlogn의 증가량이 작기 때문에, 정렬을 수행하는 비용이 크지 않습니다.
  • 정렬 후 투포인터를 사용하면 문제를 보다 간결하고 효율적으로 해결할 수 있습니다.

---

4. 투포인터 + 정렬 알고리즘의 혼합 사용

정렬 + 투포인터 알고리즘의 시간복잡도는 다음과 같습니다:

1. 정렬 단계: O(nlogn)
2. 투포인터 알고리즘 실행: O(n)

따라서, 전체 시간복잡도는 O(nlogn+n)O(nlogn + n)O(nlogn+n), 즉 O(nlogn)O(nlogn)O(nlogn)이 됩니다.

---

728x90

5. 정리

• O(n)를 사용하는 상황:
  • nnn이 매우 크고 데이터가 정렬되어 있거나, 정렬 없이도 문제를 풀 수 있을 때.
  • 연속적인 탐색이 주된 작업일 때.
• O(nlogn)를 사용하는 상황:
  • nnn이 상대적으로 작거나, 문제 해결을 위해 정렬이 반드시 필요할 때.
  • 정렬 이후 추가 작업의 복잡도가 낮아 전체 연산량이 효율적일 때.

추천 기준

• n>100,000n > 100,000n>100,000: O(n) 알고리즘을 사용하는 것을 우선 고려.
• n≤100,000n \leq 100,000n≤100,000: O(nlogn)도 무리 없이 사용 가능.

이 기준은 상황에 따라 유동적일 수 있으므로, 문제에서 요구하는 성능 조건에 따라 적절히 선택하세요!