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

LIST ALL

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

수 데이터 오름차순 정렬 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 notice   초보자를 위한 창조메뉴얼 한글문서 [7] 최재일 2005/01/30  12455 notice   소스자료실 이용안내입니다. 변혁수 2002/09/01  12391 777    창조로 아두이노를 해봤습니다. [2] 남상기 2018/02/21  5570 776    한글 초성/중성/종성 합치기 [1] 성인e 2017/11/30  16690 775    필기인식 성인e 2017/02/23  18 774    파일 <-> 비트맵 변환 성인e 2016/05/30  9164 773    반복문 속도 빠르게 [3] 성인e 2016/05/01  8890 772    행렬식 구하기 성인e 2016/03/19  9238 771    브레인퍽(Brainfuck) 인터프리터 성인e 2016/03/05  8643 770    로렌즈 끌개 성인e 2016/01/06  8402 769    색범위 추출 성인e 2015/12/10  7846 768    그레이스케일, 채도맵, 안티에일리어스드 리사이징 성인e 2015/11/30  8164 767    ETF (Edge Tangent Flow) 성인e 2015/11/27  6915 766    소벨 윤곽선 검출 성인e 2015/11/18  5958 765    이미지 90도 회전 성인e 2015/11/17  5962 764    지뢰찾기 (속도 개선) [1] 성인e 2015/11/10  5909 763    창조에 파이썬 임베딩하기 [1] 성인e 2015/10/28  5096 762    창조 일체형 성인e 2015/10/08  6999 761    인공지능 오목 [1] 성인e 2015/09/09  7607 760    얼굴검출 (Face Detection) 성인e 2015/09/09  13 759    [crt2py] 만델브로트 성인e 2015/04/09  14 758    crt2py로 그레이스케일 빠르게 하기 [1] 성인e 2015/03/01  139 757    이미지 합☆체 [2] 성인e 2014/06/25  6180 756    두 이미지가 어느정도 비슷한지 검사 성인e 2014/04/19  4783 755    프로그램 만드는 베이스 성인e 2014/04/17  5208
	LIST ALL   1 [2][3][4][5][6][7][8][9][10]..[32] Next

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