알고리즘 잘 아는 사람 있음?

[익명(121.148)]

퀵 소트(정렬)의 최악의 경우인 수행시간 구하는 건데

맨 윗줄에서 세타n이 왜 나온 건지 모르겠음

분할하는데 걸리는 시간이 왜 n에 비례함??

그냥 상수시간 아니야? 

[나트륨찡(alphauri)]

분할을 n개를 한바퀴 돌면서 하니깐

[나트륨찡(alphauri)]

최종: n개를 n바퀴

[익명(124.28)]

코드안봤노

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(121.148)]

병합정렬은 배열을 나눌 때 비교하지 않고 나누기 때문에 상수시간이 걸리는 거고, 퀵정렬은 피봇을 기준으로 대소비교를 해야하니까 n1번 비교를 해야해서 n에 비례하는 거였네요 감사합니다

[익명(175.223)]

n번 돌아야하잖어 - dc App