6장. 긍정적인 시나리오 최적화

최악의 시나리오가 아니라, 모든 시나리오를 고려..? 평균적인 시나리오를 고려

6.1 삽입 정렬

삽입정렬(insertion sort)

• 첫 번째 패스스루에서 임시로 인덱스1(두번째 값)을 삭제하고, 이 값을 임시 변수에 저장한다. 인덱스 1은 공백이 된다. 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.
• 공백 왼쪽에 있는 값과 임시 변수에 값을 비교하다. 공백 왼쪽의 값이 임시변수보다 크면 그 값을 오른쪽으로 옮긴다. 비어있는 왼쪽으로 임시변수를 넣는다.
• 마지막 인덱스에서 패스스루를 할때까지 패스스루를 반복한다.

6.3 삽입 정렬의 효율성

삽입정렬은 네종류의 단계를 거침: 삭제, 비교, 시프트, 삽입

• 비교: (N^2)/2
• 시프트: (N^2)/2
• 삭제: N-1
• 삽입: N-1
  모두 더해주면: N^2+2N-2 단계

=> 다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 가장 높은 차수의 N만 고려한다.
(값이 커질수록 작은 차수의 영향력이 미미해지므로)

버블정렬과 삽입정렬은 N^2, 선택정렬은 (N^2)/2.
그럼 2배 빠른 선택정렬이 가장 나은 방법일까?

6.4 평균적인 경우

최악의 시나리오에서는 선택정렬이 더 유리. 그러나, 평균 시나리오 역시 중요하게 고려해야 함.

	최선의 시나리오	평균 시나리오	최악의 시나리오
선택 정렬	N^2/2	N^2/2	N^2/2
삽입 정렬	N	N^2/2	N^2

거의 정렬된 데이터를 다룰 경우 = 삽입 정렬이 유리
대부분 역숙인 데이터를 다룰 경우 = 선택 정렬이 유리
어떤 데이터가 들어올지 모르는 경우 (=기본적으로 평균적인 경우 = 둘다 비슷.

대부분 평균적인 경우가 발생함을 고려하면서, 최선의, 평균, 최악의 시나리오를 구분해서 알고리즘을 최적화해야 한다.

---

7장. 일상적인 코드 속 빅오

일반적으로 O(N^2)은 느리게 본다.
다양한 코드에 대한 빅 오 표현법을 찾아본다.
모두 다 적는건 비효율적인 것 같아 인상적이었던 예제만 기록한다.

7.8 여러 데이트 세트 구하기

한 배열의 모든 수와 다른 배열의 모든 수를 곱하는 코드.

function twoNumberProducts(array1, array2) {
  let products = [];

  for(let i = 0; i < array1.length; i++) {
    for(let j = 0; j < array2.length; j++) {
      products.push(array1[i] * array2[j]);
    }
  }

  return products;
}

한 배열의 크기를 N, 다른 배열의 크기를 M이라 할 때, O(NM)
case1) N=9, M=1인 경우 : O(N)
case2) N=5, M=5인 경우 : O(N^2)
=> O(NM): O(N)~O(N^2)

7.9 암호 크래커

암호 풀이를 위해 n이 3인 경우, ‘aaa’부터 ‘zzz’까지 모든 문자열을 순회하도록 루프를 설정하는 경우
=> N이 문자열의 길이일 때 26^N
=> N이 1씩 늘어날 때 마다 26단계가 증가한다.