05-06 빅오, 긍정적 시나리오 최적화

선택정렬

비교, 교환 두종류의 단계를 포함한다.

패스스루의 최솟값이 이미 올바른 위치에 있으면 아무것도 하지 않아도 되지만 최솟값이 올바른 위치에 있지 않으면 교환해야한다.

1. . 배열의 각셀을 왼쪽부터 오른쪽방향으로 확인하면서 어떤값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다
2. 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다.

1. 배열 끝에서 시작하는 패스스루에 도달할 때까지 패스스루를 반복한다. 마지막 패스스루에서는 배열이 완벽히정렬된다.

• 교환: 패스스루당 최대 한 번 필요
• 선택정렬은 버블정렬보다 두배 더 빠르다.

상수무시하기

빅오표기법은 상수를 무시한다.

빅오로는 똑같이표현되는 두 알고리즘은 100배 차이 날 수 있다.

빅오표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.

데이터가 늘어날 때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하다.

• 빅오를 사용해 알고리즘이 대체로 얼마나 효율적인지 알 수 있고, 빅오에서 같은 분류에 속하는 두 알고리즘 도 비교할 수 있다.

삽입정렬

삭제, 비교, 시프트, 삽입의 단계가 필요하다.

버블과 선택 정렬은 둘 다 효율성은 같지만. 실질적으로 선택 정렬이 두배 더 빠르다.

효율성을 분석하려면 각 단계별 총합을 계산해야한다.

1. 첫 번째 패스스루에서 임시로 인덱스 1의 값을 삭제하고 임시변수에 저장, 1엔 값이 없으니 공백이 생긴다.
2. 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다.
   1. 공백 왼쪽에 있는 값이 임시변수 값보다 크면 오른쪽으로 시프트

3. 임시로 제거한 값을 현재 공백에 삽입한다.

1. 인덱스 2의 값을 임시변수에 저장, 시프트를 반복한다.

총합은다음과같다.

N ?번/ 비교와시프트를합쳐서

+삭제N- 1번 + 삽입N- 1번

N?+2N- 2단계

 

일단O(N2+N)으로단순화

 

평균적인 경우

실제로는 대부분 평균시나리오가 일어나기 때문에 평균시나리오를 중요하게 고려해야함.

거의 정렬된 데이터를 다룰거라고 가정할 수 있는 이유가 있다면 삽입정렬이 낫다.

 

• 최선의, 평균, 최악의 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것 만큼이나 사용자 요구에 맞는 최적화 알고리즘을 고르는 핵심기술이다.