알고리즘) 퀵소트 시간복잡도(부가적인거)

 

 

 

이진 검색 시간복잡도

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

데이터 개수가 딱 2, 4, 8, 16개처럼 예쁘게 안 떨어지고, 7개나 10개일 때는 어떻게 계산하지?

 

 

 

 

 

 

 

큌소트 두가지방법

 

 

 

• Hoare 방식: 양 끝에서 다가오기 때문에, 교환(swap)은 반드시 '피벗보다 큰 놈'과 '피벗보다 작은 놈'이 서로 위치가 바뀌어 있을 때만 딱 한 번 일어납니다.

 

 

 

 

 

 

 

 

 

 

"정렬"은 기본적으로 오름차순인가요?ㅇㅇ

 

 

 

 

 

 

 

퀵 정렬은 **"피벗이 데이터를 얼마나 반반하게 잘 나누느냐"**가 생명입니다.

분할정복이니깐 

 

 

 

수학적인 부분들

 

 

 

 

단위연산: S[i]와 key와의 비교

• 알고리즘의 속도를 측정할 때, 가장 핵심이 되는 동작 하나를 정해서 횟수를 셉니다.
• 퀵 정렬의 분할(Partition)에서는 **"피벗(key)이랑 배열에 있는 숫자(S[i])를 비교해서 큰지 작은지 따져보는 것"**이 가장 중요한 일입니다.
• 이걸 몇 번 하느냐가 곧 이 알고리즘의 성능이 됩니다.

 

 

n자체가 size임

인덱스가 아니라 

 

 

퀵소트 시간복잡도 -최악 

 

 

 

 

 

 

 

 

 

 

큌소트시간복잡도 -평균적-1,2단계

 

피벗은 정렬이 끝났으니 제외한다"

 

 

 

이거 i,j가는게 아 끝까지 가야해서 n-1인건가ㅇㅇ

 

 

 

 

홀수일때도 2번 등장하네 

 

평균일때 -3단계

sn-sn-1=an

 

 

 

 

 

 

 

 

(근데 걍 그대로 빼네 

 

 

 

 

4단계

 

 

 

 

 

 

 

 

 

 

 

 

 

점화식 구했는데 갑자기 왜 더하냐

(애초에 평균 구하고 싶었던게 우리 목적)_

 

 

 

 

 

 

 

 

 

 

치환 돌려놓기

 

 

(마지막)

 

 

의의

 

 

 

 

 

---

 

 

 

 

 

 

계수인 2는 따로 뺴고, 분리할때, 빼기를 분리하는거네 (어차피 분모 같으니깐 )

 

 

 

dd

 

 

(뒤의 분수부분만 1...n까지 해주면 안되고 

an

an-1부분도 1...n까지 넣으니깐, 

an-1사라짐 

 

그래서 

an=...형태로 되게 됨