누구나 자료 구조와 알고리즘 | 빅 오를 사용하거나 사용하지 않는 코드 최적화 | 선택 정렬

✔️선택 정렬

• 선택 정렬 방법
  • 앞에서부터 순서대로 돌면서 최솟값이 있는 인덱스를 변수에 저장
  • 다 돌았을 때 시작 인덱스와 변수에 저장된 인덱스의 값을 바꾼다.
  • 배열 끝에서 시작하는 패스스루에 도달할 때까지 계속 반복
• 선택 정렬 실제로 해보기

 

• 선택 정렬의 효율성
  • 버블 정렬의 단계 수 / 2 = 선택 정렬의 단계 수
  • 즉, 선택 정렬의 단계 수는 O(N^2) / 2이다.
• 상수 무시하기
  • O(N^2 / 2) 이지만 빅오 표기법은 상수를 무시한다.
    • 즉, /2를 버리고 O(N^2)로 표기한다.
  • 그래서 버블 정렬과 선택 정렬의 실제 성능 차이는 크지만 빅 오 표기법만 봤을 땐 둘의 단계 수가 같다.
    👉🏻 빅오만 보고 성능을 판단하기 쉽지 않다는 뜻이다.
• 빅 오의 또 다른 개념
  • 빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.
    즉, 일반적인 카테고리로만 말한다.
    
  • O(N)이랑 O(N^2)를 비교할때 기본적으로 효율성 차이가 너무 커서 O(n)이 뭐든 사실상 중요하지않음
  • 그래서, 같은 카테고리에 속한 알고리즘이라도, 한단계 더 들어가서 어떤게 더 많은 단계가 필요한지, 더 적은 단계가 필요한지 알아봐야한다.
• 어떤 단계를 세어야하는지 결정하는 법을 빅 오의 표현이라고 했는데, 어떤 단계가 중요할까?
  • 모든 단계가가 중요하다
  • 단지 빅 오 용어로 단계를 표현할 때 상수를 버리고 표현식을 단순화할 뿐이다