Algorithm Basics

시간 복잡도

• 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘 선택
• 주어진 문제를 해결하기 위한 연산 횟수
• 표기법
  • 빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기
  • 빅-세타: 보통일 때(average case)
  • 빅-오( O(n) ): 최악일 때(worst case)
• 코딩 테스트에서는 worst case 고려해서 따져주기
  • ex) 버블 정렬 vs 병합 정렬
• c++ 1억번 연산 = 1초 (대략)

시간 복잡도를 바탕으로 코드 로직 개선하기

작성된 코드의 비효율적인 로직을 개선하는 바탕으로도 사용가능. 시간 복잡도 도출 기준

• 상수는 시간 복잡도 계산에서 제외 O(n) ~= O(3n)
• 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. (for, while..) 이중 for문 등.

Summary

• 시간 복잡도는 최악의 케이스 O( )
• 시간 복잡도 도출
  • 상수 X
  • 가장 많이 중첩된 반복문 기준
• 알고리즘 선택 기준
  • 시간초과시 내 비효율적 코드가 어디인지 판단 기준

---

Next

Debug (C++)