창조유저그룹-커즈닷컴

소스자료실
- 창조 소스를 공유하는 곳입니다. 첨부가능 확장자는 *.zip,*.rar,*.arj,*.exe,*.jpg,*.png,*.gif,*.cuf,*.nhp,*.nhw 입니다.

Posted by 성인e

2012-03-24 15:43:20, Hit : 5719

수 데이터 오름차순 정렬

File #1 : arrange.zip (631.9 KB) Download : 80

전에 만들었던
http://cugz.sjworks.net/bbs/zboard.php?id=pds_sc&no=673
보다 훨씬 빨라졌습니다..

이론상 Log_2 t 만큼으로 단축됩니다.
예를 들어 본래 1024 초 걸렸다면 이젠 10초 걸리게 됩니다..

지상현 2012-03-24 PM 5:55:06


흠. 삽입정렬의 일종 같네요. 말씀하신대로, 삽입하는 곳을 찾는 방법은 O(n)에서 O(log2_n) 으로 바뀌었는데, 항목을 정렬하는 것 자체는 여전히 O(n)입니다. 항목을 하나 하나 골라서 이진검색으로 삽입할 곳을 찾아 넣기 때문에 O(n + log2_n) = O(n)입니다. 이론적으로도 그렇고 실제로 돌려보면 자료가 5배 증가했을 때 걸리는 시간도 5배 정도 더 걸리니, 다시 한 번 확인해보시라는 차원에서 글을 적어봅니다.

지상현 2012-03-24 PM 6:15:44


잘못적었네요. O(n + log2_n)가 아니라, O(n * log2_n) 또는 O(nlog2_n) 입니다.

성인e 2012-03-25 AM 1:14:06


자료의 갯수 n이 아니라 그 전 알고리즘에서 걸리는 시간 t 를 기준으로 서술했습니다... 삽입할 곳을 찾는 방법이 O(n)에서 O(log2_n)으로 바뀌었고, 항목을 정렬하는 것이 O(n)이라고 하셨습니다. n이 자료의 갯수인지, 비교할 갯수인지도 혼용되어있군요.

성인e 2012-03-25 AM 1:31:38


그래서 시간복잡도 표기도 틀리셨네요. 만약 오른쪽 리스트에 아무것도 없이 n개를 정렬하기 시작했다면 log2(1)+log2(2)+...+log(n-1)+log(n) 해서 복잡도는 O(log2(n!)) 입니다..