덧셈 횟수가 제가 구한게 맞는건가요 ㅠㅠ?

HJH_

2011.11.11 00:47:28

조회 48 추천 0 댓글 1

def multfast(m, n):

if n == 1:

return m

elif (n % 2) == 0:

# fast 방법 사용

# 2 * m * (1 / 2) * n = m * n이므로 값에 영향을 미치지 않으면서

# n의 값을 절반으로 줄이므로, 계산 횟수를 줄일 수 있음

return multfast(double(m), halve(n))

else:

# fast 방법을 쓸 수 없음 -> 단순 무식 방법 사용

return m + multfast(m, n-1)

return multfast(m, n)

파이썬으로 이러한 함수를 만들었는데..

덧셈 횟수가 log n에 비례한다고 하더군요...

전문적 표기로는 O(log n)이라고 하는거 같은데.. 아무튼..

제가 계산을 해봤는데..

# multfast(23, 14)

# -> multfast(46, 7)

# -> 46 + multfast(46, 6)

# -> 46 + multfast(92, 3)

# -> 46 + 92 + multfast(92, 2)

# -> 46 + 92 + multfast(184, 1)

# -> 46 + 92 + 184

# -> 322

# -> 덧셈 횟수: 3번

이렇게 되면 덧셈 횟수가 3번이 맞는건가요 ㅠㅠ?

또, O(log n)에서 log의 밑은 도대체 2인건가요 10인건가요 아니면 상관이 없나요 ㅠㅠ?

바이너리 그쪽 계통 알고리듬이 log n인걸 보면 밑이 2인거 같은데..ㅠㅠ

답변해주세요 횽들 ㅠㅠ

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	대박 날 것 같아서 내 꿈에 나와줬으면 하는 스타는?	운영자	25/11/17	-	-
AD	대학생 필수템! What's in my Bag	운영자	25/11/21	-	-
287709	자바공부하면 si로 가는 지름길임?? [4]	po게이wer	11.11.11	205	0
287708	자바스크립트 급질요 왜 현재시간이 10월로 나오죠 [3]	저급함(68.107)	11.11.11	71	0
287707	헤헤 난 이따 3시부터 여자 면접 본다 헤헤 [4]	거칠게	11.11.11	150	0
287706	필기 시험 3분 전입니다 고갱님~ [5]	거칠게	11.11.11	103	0
287705	생각해 보면 IT 기업처럼 자유로운 회사도 드문거 같다. [1]	거칠게	11.11.11	174	0
287704	c언어 자료구조 배웠던 횽님들 부탁이있음 ㅠㅠ [3]	북극곰(121.187)	11.11.11	101	0
287703	지금 이순간 난 필기시험 감독을 하고 있다 [2]	거칠게	11.11.11	74	0
287702	설마 찌질하게 빼빼로 따위나 주고 받는건 아니겠지?? [1]	거칠게	11.11.11	64	0
287701	선배님들 도와주십쇼 전 학생입니다 [10]	delmon(119.67)	11.11.11	127	0
287700	형들 서버개발자가 필요한 디비쪽능력이 뭐에요? [3]	킁킁(121.138)	11.11.11	82	0
287699	기술면접에서 gc가 언제 동작하는지를 묻는다면 [3]	ㅂㅈㄷ(210.178)	11.11.11	146	0
287698	리얼포스 지름 후기 [5]	알탱o	11.11.11	149	0
287697	버스에서 ios 업글했당 [1]	분당살람	11.11.11	75	0
287696	리얼포쓰 샀다 [6]	알탱o	11.11.11	105	0
287695	리눅스 기반 프로그램 설계 할건데 재치있는 조이름 없을까요?ㅎㅎ [9]	런공	11.11.11	231	0
287693	점심들은 먹고 일하냐? [2]	21C노가다	11.11.11	85	0
287691	★★★ paran 호스팅에 홈페이지 제작 10만원 [8]	매미(211.110)	11.11.11	146	0
287690	니네 WAC이나 K-App 잘 아는 놈 있냐 [18]	PoRO	11.11.11	171	0
287688	★★★ VBA 잘하는분 코드작성알바 10만원 [2]	매미(211.110)	11.11.11	312	0
287687	점심시간에 용산이나 가야것다.... [3]	알탱o	11.11.11	120	0
287686	오늘 촛불 할 사람? [4]	_가나다	11.11.11	85	0
287684	빼빼로데이때 빼빼로 말고 소고기 스테이크 받고 싶어 [1]	알탱o	11.11.11	45	0
287683	굿모닝 [4]	호주종자(101.171)	11.11.11	65	0
287682	20111111 11:11 9분전 [1]	ㅋ(211.222)	11.11.11	46	0
287678	씨언어 이것좀 봐줘 횽들 ㅜㅜ [3]	탁이★	11.11.11	89	0
287676	보통 첫직장 잡고 몇년후에 결혼들 하냐? [3]	dd(59.9)	11.11.11	129	0
287675	오늘이 천년에 한번 온다는 솔로날임니다 [2]	HarlemLuiah	11.11.11	62	0
287672	죤나 아침이야 형들~ [3]	!@＃ㅇㅇ	11.11.11	46	0
287671	몰라서 묻는 건데 삼성 sw멤버쉽이 모하는 거임? [2]	분당살람	11.11.11	708	0
287670	빼빼로데이라는건 [4]	Gavi_cp	11.11.11	61	0
287669	프갤은 프갤답게 빼빼로 데이를 즐기면 되지	쿄스케	11.11.11	53	0
287667	싱글턴패턴에서 말이야 &리턴, *리턴 차이가 뭘까 각각의 장단점이랑? [3]	아쥬	11.11.11	72	0
287663	횽님들 간단한 타이머 프로그램이 오류가 발생하는데 이거 좀 봐주세요 [1]	생생물우동(222.233)	11.11.11	40	0
287662	넷북 싼거 하나 사려는데 셀러론 듀얼코어 apu e 둘 중에뭐가 나아요? [1]	fsdf(182.213)	11.11.11	114	0
287660	입갤) 미연시게임을 프로그래밍하고싶습니다 [7]	다림줄	11.11.11	146	0
287658	자바 마우스리스너 막 배우기 시작했는데 오류가 납니다.	컴쟁이(222.121)	11.11.11	63	0
287657	자료형 변환 문제 질문있습니다. [3]	hd2	11.11.11	58	0
287655	원래 ofstream 에서 open해서 글쓸때 있던 내용 지워지는거야??	Chew	11.11.11	46	0
287654	쮸쮸빠 형 나 큰일났어!! [6]	큐아큐아큥(125.131)	11.11.11	119	0
287652	☆★☆★대세는 이문동 쮸쮸빠! 대세는 이문동 쮸쮸바!!!★☆★☆ [2]	큐아큐아큥(125.131)	11.11.11	77	0
287651	Xcode 3점때 쓰는 형 있음? [1]	척추접이(61.247)	11.11.11	63	0
287650	자살춤며짤임? [1]	^0^	11.11.11	71	0
287649	갤러들아 뭐 하나 물어보고싶은거 잇는데 꼭 대답좀해주라.. [11]	퍼플덕후(1.11)	11.11.11	174	0
287648	지금 대학생들, 애인사귀면 100일날 꼭 만나야된다 [1]	^0^	11.11.11	139	0
287647	VC++ 진짜 NMAKE 오류 미칠것같음 어캄? [1]	솔라리스와리눅스	11.11.11	100	0
287645	횽들아 나 호구임? 여자사람 얘기임 [27]	늅늅ㅂ(211.117)	11.11.11	235	0
287644	프갤형들 특히 실무나 현장에서이하는 형들에게 중요한 질문이있어	사랑해요프갤(121.140)	11.11.11	44	0
287642	횽들, VS 2010 pro K 쓰는중인데 ; 인텔리센스 ;; [5]	Re-FEEL	11.11.11	82	0
287641	구조체 넘 어려워요 ㅠㅠ // 고수님들 헬프좀 [2]	24.윤피	11.11.11	78	0
287640	다이렉트 x 9.0 버퍼를 만지다 기이한 초미스테리현상을 발견했습니다?? [15]	큐아큐아큥(125.131)	11.11.11	172	0