<aside> 💡 정렬, BigO

</aside>

BigO

알고리즘

알고리즘은 어떤 문제를 풀기 위한 절차나 방법

• 주어진 ‘입력’을 ‘출력’으로 만드는 과정
• 알고리즘의 각 단계는 구체적이고 명료해야 한다.

• 계산 복잡도 : 어떤 알고리즘의 계산이 얼마나 복잡한지를 나타내는 정도 → 가장 많이 사용하는건 빅 오 표기법

빅오 표기법은 알고리즘의 효율성(계산 복잡도)을 표기해주는 표기법이다.

• 필요한 계산 횟수를 정확한 숫자로 표현하느 것이 아니라 입력 크기와의 관게로 표현
• 예시 ) 입력 크기 n에 따라 덧셈을 두 번씩 하는 알고리즘도 O(2n)이 아니라 마찬가지로 그냥 O(n)
• 예시2 ) O(3n(^2)+n + 2) = O(n(^2))
• 입력 크기 n과 필요한 계산의 횟수가 무관하다면 O(1)

정렬

• 평균적으로 O(n(^2))
  • 선택 정렬
  • 버블 정렬
  • 삽입 정렬
• O(nlogn)
  • 병합 정렬
  • 퀵 정렬

선택 정렬