04 빅오로 코드 속도 올리기

빅오를 사용하면 세상에 존재하는 범용 알고리즘을 비교할 기회가 생긴다

 

4-1

버블정렬 버블정렬은 첫 항목과 두 번째 항목을 비교하고(왼 값이 오른 값보다 크면)두 항목을 교환한다.

이를 배열의 끝까지 반복한다.

정렬되지 않은 값 중 가장 큰 값,버블이 올바른 위치로 가게 되기때문에 버블 정렬이라고 부른다.

 

 

---

 

버블 정렬 알고리즘은 두가지 중요한 단계가 있다.

 

비교

어느 쪽이 더 큰 수인지 비교한다

ex)배열의 원소가5개다.첫 번째에서 두수의 비교를4번,두 번째에서3번,세 번째에서2번,네 번째에서1번 4+3+2+1=10의 비교다. (n-1)+(n-2)+(n-3)....+1번 비교

 

 

교환

정렬하기 위해 두 수를 교환한다

ex) 배열이 내림차순으로 정렬된 최악의 시나리오라면 비교마다 교환을 해야한다. 즉 비교 10이면 교환 10 총 20단계이다.

원소 5개 역순 이면 4+3+2+1=10 번의 비교, 더불어 교환 10회 총 20단계라는 소리다.

 

 

원소 20개면 19+18...+1=190비교이고, 190교환 총 380단계 이는 원소 수가 증가할 수록 단계가 기하급수적으로 늘어난다. 버블의 빅 오의 효율성은 O(N)이다. 이를 2차 함수라고 부른다.