창조유저그룹-커즈닷컴
Window close
ID :     PASS :   
   
  처음으로
  창조
  창조 소개
창조 다운로드
CUGz.com 소개
온라인 도움말
  커뮤니티
  가입인사
자유게시판
Q/A게시판
TIP/TECH
열린강좌
자주하는질문
아이디어게시판
  자료실
  소스자료실
프로그램자료실
기타자료실
명예의 전당
이미지 자료실
  지원/기타
  표준용어재정
구글 웹서치  
관리자 전용


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


LIST ALL
Posted by 성인e2012-03-24 15:43:20, Hit : 5669
수 데이터 오름차순 정렬
File #1 : arrange.zip (631.9 KB)   Download : 80
Post URL : http://cugz.sjworks.net/bbs/zboard.php?id=pds_sc&no=862
전에 만들었던
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!)) 입니다..
지상현   2012-03-25 PM 6:53:11  
잘 몰라서 죄송합니다.
김환욱   2012-11-27 PM 2:00:16  
ㅎㅎㅎㅎ
LIST ALL               GO TO THE TOP


N
   Subject
Posted by
Date
H
729
   Exposure(노출), Contrast(대비), Blur 조절
성인e 2013/01/31  4189
728
   닷지
성인e 2013/01/23  4351
727
   보로노이
성인e 2012/12/28  4364
726
   'Sleep' 대신 '지연' [2013,1,1,4:50 새로 만들어 재업로드]
바람 2012/12/27  4393
725
   동적 생성으로 구현한 '시간문자창보여' & '큰문자창보여'[2013, 1, 4 04:30 업데이트]
바람 2012/12/27  4705
724
   로프 구현
성인e 2012/11/25  4401
723
     [re] 천(cloth) 구현
성인e 2013/03/16  3856
722
       [re] 향상
성인e 2013/03/19  3834
721
         [re] 버그 고침
성인e 2013/04/26  3645
720
   마우스 매크로
성인e 2012/07/15  7768

   수 데이터 오름차순 정렬 [6]
성인e 2012/03/24  5669
718
   여백없애기
성인e 2012/03/04  5000
717
   [0.9b] CSV 파일 읽고 쓰기 (ㅎ문자표)
지상현 2012/01/05  7927
716
   [0.9b] RichEdit line insertion error 회피 / 추가 속도 비교 [1]
지상현 2011/12/31  8807
715
   [0.9b] 클립보드 데이터 가져오기 (Api) [6]
지상현 2011/12/29  6656
714
   덜덜덜덜
성인e 2011/12/06  4708
713
   life game
성인e 2011/09/26  4903
712
   미로찾기
김대명 2011/09/05  5019
711
   십이지로 날짜 표시하기
김대명 2011/08/20  5225
710
   아주 간단한 SQL 주소록 예제 [4]
지상현 2011/07/14  6101
709
   단진자&이중진자
성인e 2011/06/12  5868
708
   좀비 죽이기 게임
김대명 2011/06/08  6316
707
     [re] 좀비 죽이기 게임
김대명 2011/08/15  6201
706
   여러가지 행렬 연산
성인e 2011/05/22  5251
705
   베지어 곡선 (bezier curve)
성인e 2011/05/13  5534
LIST ALL   Prev [1][2] 3 [4][5][6][7][8][9][10]..[32] Next
Copyright 1999-2024 Zeroboard / skin by reedyfox in miniwini style
로그인
지우개 Expert 3.0
제작자 : 천호성 님 [LINK]
로그인
대박로또2005
제작자 : 최재일 님 [LINK]
로그인
1박종훈15292 점
2지상현8809 점
3손상진7388 점
4권선중6060 점
5이진백5174 점
로그인
가입일닉네임
05/31김동률
03/31홍형기
09/01o00pp99oo
12/27이재민
11/20이희철
로그인