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

HJH_

2011.11.11 00:47:28

조회 53 추천 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	-	-
287806	상대컴에 바이러스 심는게 가능한가요? [3]	모지혜	11.11.12	66	0
287805	역시 질문글은 조회수도 낮고 답글도 없고 ㅠㅠ [1]	Lover♥	11.11.12	40	0
287804	개발자 형들 내 이야기좀 들어줄래? [8]	형아(211.245)	11.11.11	167	0
287803	곽노현팀장은 왜 여기서 노느긔?	123321123(211.201)	11.11.11	37	0
287802	자바로 무한루프 구성할 때 이러한 구조가 맞는거야? 50프레임이라고 할	Lover♥	11.11.11	61	0
287801	으헝 힛자점 [2]	풀개미'ㅅ'	11.11.11	83	0
287800	성폭력기사좀 안나왔으면 좋겠다 [3]	금고래	11.11.11	114	0
287798	앱이야기 : 사용자들은 생각보다 단순한거 같다.	시불라미	11.11.11	117	0
287796	MFC 왕초보인데요. 빠르게 해답을 구할 곳이 요기뿐인것 같아 질문드려요 [6]	궁금함(218.235)	11.11.11	136	0
287795	노츠라는 그룹웨어 하는 분 있나요	-0-(210.216)	11.11.11	56	0
287794	빼빼로데이엔 뭐다?	System32	11.11.11	80	0
287793	***** VBA 알바 10만원 모집 [6]	vba(219.240)	11.11.11	497	0
287792	정보보안갤러리의 개설을 신청중입니다^~^ [5]	정수정•‿•	11.11.11	100	0
287790	웹 호스팅 왕 초보.... 좀 물어볼게 형아들 [4]	형아(211.245)	11.11.11	89	0
287789	근래에 이직한 횽 있으면 답글 좀! [2]	ㄱㄱ(112.214)	11.11.11	57	0
287788	자바로 유리한점과 불리한점좀 [7]	박구	11.11.11	195	0
287787	프갤형들 나 휴학하고 공부하고있는데 내미래는 이래~	외톨이(119.192)	11.11.11	65	0
287786	C++ Opencv 사용해서 안드로이드 어플 개발할라는데 좀 아는사람?? [2]	졸프(203.226)	11.11.11	143	0
287782	Q) visual c++ 2010 환경설정 질문 [1]	지은(121.183)	11.11.11	61	0
287781	C++ Opencv 사용해서 안드로이드 어플 개발할라는데 좀 아는사람??	졸프(203.226)	11.11.11	46	0
287778	삼성소프트웨어 멤버십 하는 성님들있나여 [2]	저격甲	11.11.11	280	0
287776	자바 고수형들 미천한 저에게 한줄기 빛과 소금같은 가르침좀 주세요 [1]	OpenUp(112.155)	11.11.11	73	0
287775	배열에 = 이용해서 대입하는거랑 scanf로 입력받는거랑 뭐가 다름? [9]	저격甲	11.11.11	105	0
287774	입개르	증인닉고	11.11.11	29	0
287773	횽님들 간단한 타이머 프로그램 오류 좀 도와주세요	생생정보통(222.233)	11.11.11	57	0
287769	아 이거 진짜 어떻게 써야됨? [2]	SPlCA	11.11.11	74	0
287767	개발잔데 연봉이 [2]	이런개새끼	11.11.11	179	0
287763	애들아 씨발 잘 놀아라 난 소고기 먹으러가 히히히히히히 ㅇvㅇ	PoRO	11.11.11	54	0
287761	형들!! 잘생긴 형들!! 이것좀 알려주세요 ㅠ_ㅠ 그럼 여친생김.. [8]	342(121.139)	11.11.11	132	0
287759	형들 컴공 졸업하면 취직 뭐해? [2]	d(119.197)	11.11.11	159	0
287758	형들...나 이번에 정말 중요한 교훈을 얻었어 [1]	Dawnwalkre	11.11.11	68	0
287756	오늘 회식 ㅇvㅇ 히히 [9]	PoRO	11.11.11	87	0
287754	바보플머의 '디자인패턴과 객체지향 비급' 업데이트! [2]	바보플머(119.207)	11.11.11	94	0
287752	독수리 타법! 끼루끼룩 [5]	봊ㅣ구멍가게	11.11.11	82	0
287751	전간디님이 야근/특근비로 110만원을 획득했습니다 [13]	전간디	11.11.11	151	0
287747	형 자바 컴파일러 머써 [4]	봊ㅣ구멍가게	11.11.11	102	0
287746	오늘이 천년에 한번인 11년 11월 11일 이라는데 백년에 한번아님? [5]	뒹그르르	11.11.11	123	0
287745	자바로 금융권취업하면 뭐맹글어요? [2]	^0^	11.11.11	134	0
287742	형님들 아까 sed 물어본 아인데 [1]	하루살이(210.125)	11.11.11	55	0
287740	자바공부중인데 변수 질문좀 할게요 [29]	ㅇㅇ(222.113)	11.11.11	209	0
287739	꿈의연봉 - 200 = ?	ㅁㄴㅇㄹ(115.137)	11.11.11	108	0
287738	너무합니다욬ㅋㅋ 꼭좀 알려주세요.. 자바 이벤트 리스너..ㅠㅠ [12]	342(121.139)	11.11.11	196	0
287736	ㅠㅠ 포트폴리오 쓰는거 너무 어렵다 [2]	ㅁㄴㅇㄹ(115.137)	11.11.11	132	0
287735	형들 내가 쓰레드는 거의 안써바서 잘 모르는데여 질문염 [8]	아쥬(61.111)	11.11.11	105	0
287734	자신감 없는 컴공인들이여 보거라. [1]	망나니(122.202)	11.11.11	141	0
287733	아래 알바모집하는 놈 같은 년들이 주로 착각하는거 [2]	알탱o	11.11.11	125	0
287732	vba 아시는분 이것좀 도와주세요 [3]	검	11.11.11	74	0
287731	으하 10시출근 5시퇴근 [2]	알탱o	11.11.11	72	0
287729	페이지파싱을 하려는데 [3]	ㅂㅈㄷ(210.178)	11.11.11	106	0
287728	아쉬바 자바 C++ 등 프로그래밍언어 전부 유료화 됬으면 좋겠다 [6]	Stan(220.244)	11.11.11	224	0