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

HJH_

2011.11.11 00:47:28

조회 51 추천 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/24	-	-
AD	따뜻한 겨울나기! 방한용품 SALE	운영자	25/11/27	-	-
288215	히발라야 레알 듸즤겄네 - _-) [2]	땡칠도사	11.11.15	98	0
288214	방금 글올렸는데 여기서 어떻게 해야할까 ㅜ 돌파구가 안보여 ㅜ [11]	ㅇㅇ(110.11)	11.11.15	130	0
288213	형들 C언어 파일 입력좀 도와줭 [9]	dd(211.196)	11.11.15	122	0
288212	여기서 국어편차 수학편차 어떻게 할까 ㅜㅜ [2]	ㅇㅇ(110.11)	11.11.15	56	0
288211	아.. 과제셔틀은 웁니다.. [1]	Aven	11.11.15	67	0
288210	죽겠다...ㅡ.,ㅡ	이문동쮸쮸바	11.11.15	47	0
288209	프갤형들 [3]	ㅇㅇ(112.171)	11.11.15	77	0
288208	날씨가 추워지니 벌써 과메기가 나왔군... [1]	이문동쮸쮸바	11.11.15	75	0
288207	개 씨팔 [2]	PoRO	11.11.15	51	0
288205	형들 제발가르켜주세요 [1]	허졉(115.140)	11.11.15	43	0
288202	헬지 유플러스 [1]	sxvc(124.49)	11.11.15	42	0
288200	인생사 새옹지마	고기(58.122)	11.11.15	52	0
288199	데이터 커뮤니케이션 강의 [1]	三didas	11.11.15	45	0
288198	동원참치캔, 런천미트 캔 [1]	5ㅁㅁ(183.101)	11.11.14	28	0
288197	느그들 대머리 사건 대법원 판결 난거 봤냐? [2]	시불라미	11.11.14	165	0
288195	게임 프로그래머가 꿈이고 1995년생 17살인 사람 봐주세요!!!!!!! [17]	하이(58.148)	11.11.14	331	0
288194	으헝하앟 API ... [6]	RedRum	11.11.14	103	0
288193	2010 사용법좀 ;;;; [6]	ㅇㅇ(121.128)	11.11.14	106	0
288191	아옳아롱호호롱로롷	ㅁ머(125.177)	11.11.14	25	0
288189	항상 반드시 최대한 오래 살아라.	ㄷㄹ(211.189)	11.11.14	37	0
288188	형들 C언어 질문좀 받아줘 [10]	스카치테이프(175.117)	11.11.14	123	0
288185	횽등 stl 시간복잡도 잘하는 횽들 없나? 인터넷 찾아도 찾기가 힘들어서 [13]	7830뭇(123.109)	11.11.14	201	0
288184	아침 해가 떴습니다~	땡칠도사	11.11.14	49	0
288183	숫자야구게임이 그냥 숫자맞추기게임이었네	길가던놈	11.11.14	55	0
288181	시볼라미 행님 ㅠ [4]	RedRum	11.11.14	57	0
288180	6.0 포기해야겠음 [2]	dd(121.128)	11.11.14	73	0
288178	API - altimage.h 에서 오류나는것 같아요... [1]	RedRum	11.11.14	598	0
288176	형들 visual c++ 6.0 서비스팩 설치가 안되 [8]	ㅇㅇ(121.128)	11.11.14	248	0
288174	c언어 질문 ㅋ [4]	123(112.221)	11.11.14	70	0
288172	DWORD 형 복사	ㅇㅇ(210.91)	11.11.14	41	0
288171	앱광고로 담배값(하루 한갑기준) 벌려면	시불라미	11.11.14	105	0
288170	3DS 살꺼야	y녀6디리(220.118)	11.11.14	50	0
288169	안녕하세요 c언어를 공부하는데 질문좀 해도 될까요 [2]	c의노예(112.221)	11.11.14	70	0
288168	시스템 프로그래밍을 좀 하고 싶은데 문제 은행? 이런거 인터넷에 없을까요 [1]	Lz(125.128)	11.11.14	66	0
288167	횽들..자바 채팅사용자 리스트에 뜨게하고싶은데..	봉봉(112.144)	11.11.14	109	0
288165	자바 JFrame 바꾸는 법?	자바(121.136)	11.11.14	49	0
288164	쇼핑몰 만드는데 후이즈가 나을까, 가비아가 나을까	프레지(210.106)	11.11.14	99	0
288162	프갤러들아 빨리 bmp크기조절하는 법좀 알려줘 [7]	이세상끝에서	11.11.14	95	0
288161	형님들 도움좀요 ㅜㅜ DWORD형을 char*형에 나눠담아야하는데... [5]	ㅁㄴㅇ(222.114)	11.11.14	97	0
288159	ssd [1]	이모군(175.114)	11.11.14	52	0
288158	페이스북같은데는 어떻게 수익이 나는거임? [8]	유동생(218.152)	11.11.14	193	0
288157	지금 돌아보니 점수맞춰서 컴공온게 잘한짓인가 생각이 든다 [7]	ㅇㅇ(112.184)	11.11.14	197	0
288156	데이터베이스 초보가 보기 좋은 책좀 알려주세요!	횽들!@@!(175.197)	11.11.14	72	0
288155	드림스파크 사우스파크 드림스파크 사우스파크 드림스파크 사우스파크 [1]	ㅇㅇ(112.184)	11.11.14	56	0
288154	1년이 끝나지 않았지만 만족스러운 1년 이었다.	치킨맛맛폰	11.11.14	71	0
288153	형들ㅋㅋㅋ 어플만들때 있자너 개발환경 뭐뭐 있어?? [7]	없쥐	11.11.14	130	0
288150	몸이 나을시간이 없는듯.. [7]	일광면(119.198)	11.11.14	201	0
288149	잠을 자도자도 졸릴땐 뭐다? [3]	System32	11.11.14	133	0
288148	stan 은 봅니다 [9]	qwer(169.229)	11.11.14	223	0
288147	질문좀 드리겠습니다	한울기둥(115.90)	11.11.14	47	0