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

LIST ALL

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

수 데이터 오름차순 정렬 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    수 데이터 오름차순 정렬 [6] 성인e 2012/03/24  5840 229    수학 함수 써먹기 -_-; 지상현 2005/08/03  5440 228    숫자만 입력되는 에디트 [1] 김대명 2011/02/28  5699 227    스도쿠 (sudoku) 맵 생성 성인e 2011/03/13  6128 226    스톱왓치 성인e 2013/05/10  4532 225    스톱워치 소스 -_-; # 다시수정 [12] 박종훈 2006/01/31  6797 224    슬라이드,시계 객체를 사용하지않고하기 [7] 이희창 2007/04/28  6326 223    시간확인 [1] 강정훈 2009/03/31  6188 222    시스템의 여러 상태 얻기.. [15] 박종훈 2006/02/24  6107 221    심심풀이로 만들어본 자동 신호등 프로그램 [1] 김대명 2010/10/18  6504 220    심장박동 그래프 (heart cardiogram) 성인e 2010/03/05  7099 219    십이지로 날짜 표시하기 김대명 2011/08/20  5355 218    쌀독 1.0 [3] Pueding 2002/09/08  8040 217    쓰잘데기 없는-_-; 계획표 그리기 [3] 지상현 2005/08/03  5534 216    아래 243번의 가계부 소스 입니다. [3] 김정수 2005/03/13  7878 215    아래 닫기버튼 삭제 추가수정해봤습니다(무단 ㅈㅅ;;) [1] 박재성[날개달기] 2005/08/29  5255 214    아이피 구하기 지겨운 딜레이 해결버젼 [5] 이수호 2003/01/31  5916 213    아이피 주소 값 얻기.... [3] 위자드 2003/01/22  5762 212    아주 간단한 SQL 주소록 예제 [4] 지상현 2011/07/14  6254 211    안녕 하세요........허접한 파일 가지구 왔어욥. [4] 강정훈 2005/06/30  6215 210    안녕하세요^^여러분들 도움으로 만들어서 올려봅니다. [4] 강정훈 2005/03/06  5754 209    알고리즘이 허술한 셰어웨어 [2] 김대명 2010/11/16  5533 208    알리미 [5] 우유중독 2006/05/28  5467 207    약간의 뻘짓 [4] 성인e 2009/04/20  6127 206    어떤분한테 도움이될 계산기소스 이시영 2003/07/21  7016
	LIST ALL   Prev [1]..[21][22] 23 [24][25][26][27][28][29][30]..[32] Next

Copyright 1999-2024 Zeroboard / skin by reedyfox in miniwini style