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

LIST ALL

Posted by 성인e 2012-03-24 15:43:20, Hit : 5748

수 데이터 오름차순 정렬 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 604      [re] [API 시리즈] 창 안에 창 빼기^^;; (MDI 창?;;) [4] 박종훈 2006/01/17  5678 603    도서관 대출반납관리 솔루션??? 김대명 2011/01/05  5690 602    아이피 주소 값 얻기.... [3] 위자드 2003/01/22  5691 601    [c++] 소캣 관련 dll 파일 소스 입니다. [2] 박재성[날개달기] 2004/06/12  5693 600    그냥...그저 그래프 그리는거(별 쓸데 없음 ..._-;;;) [5] 박종훈 2009/05/10  5695 599    Tweak Mania 1.0 [Build:532] 소스 [3] Pueding 2003/02/08  5697 598    [5]창조소스 모음..(공개하신거전부) 박재성[날개달기] 2005/07/16  5699 597    구 그리기 솟스&알고리슴(즘,듬) [1] 성인e 2009/07/23  5702 596    창을 화면의 중앙에 위치시키는 예제입니다. !미부!쿄시로 2003/02/10  5704 595    [0.9b]색상값에서 빨강,초록,파랑(RGB) 값을 분리하는 예제 지상현 2005/08/24  5708 594    오늘 API 땡기네~ 윈미에서 동영성재생시 마우스 사라지는효과 [9] 박재성[날개달기] 2005/08/29  5709 593    [창조 0.9b] 공백인 줄을 제거하는 함수 [질문 예제] [3] 박종훈 2006/11/11  5711 592      [re] 입문자용 쟁반-시계 성인e 2009/10/24  5719 591    폰트 메니아 소스;; [2] qkrwhdgns 2006/01/09  5723 590    [소스]자기가 원하는 이미지를 커서로 사용하기.. [2] 김환욱 2003/01/13  5724 589    드디어 만들었다!바탕화면 바꾸기!! 우유중독 2006/06/18  5727 588    지뢰찾기 솟스 [3] 성인e 2009/05/05  5727 587    온도변환기 [6] 이성찬 2004/09/17  5728 586    캡처기 성인e 2009/07/09  5728 585    돋보기 솟스 성인e 2009/09/19  5728 584    [0.9b]버블정렬을 이용한 리스트박스 정렬 [10] 김환욱 2004/06/20  5743 583    Library Center 1.0 소스 1차 공개 [1] 정성우 2005/01/19  5746 582    창틀무에서 창의 이동.. [7] nylon 2002/09/21  5748 581    탄성체_wired [1] 성인e 2009/09/20  5748    수 데이터 오름차순 정렬 [6] 성인e 2012/03/24  5748
	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