저 이알고리즘 때문에 12시간을 날렸어요, 도와주세요ㅠㅠ.

응애(122.202) 2011.10.12 00:53:10

조회 103 추천 0 댓글 1

KMP알고리즘에서

실패함수의 성능이 O(n)이라는데요.

왜이렇게 유도되는거죠?
n자리 패턴이 있고
i = 패턴에서 문자의 위치 일때
i의 비교횟수는 (i-1)번 이잖아요
접두부와 접미부를 비교해야 하는데 접두부는 최대 ( i-1)개의 문자를 갖으니까요.

그리고 비교횟수가 최소 1회이상이려면
i= 2 ~ 패턴길이 n 까지여야 하는데

그러면 저걸
수열 i=2~n 까지 (i-1) = 대략 n(n+1)/2 - n이 나와서
n^2/2 + n/2 - n 이 나와서
O(n^2)이 되는거 같은데...

ㅡㅡ; 제 계산에 미스가 있나요??

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

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

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	끝까지 다 본 걸 후회하게 만든 용두사미 드라마는?	운영자	25/07/07	-	-
280287	아아 헬쥐 U+ 또다시 [2]	막장갤신학생	11.10.12	58	0
280285	프갤 간만에 와서 한 3페이지 넘겨봤는데... [5]	Dynast(59.151)	11.10.12	95	0
280283	혹시 rfid장비 써본형 있음?	laoshanlong	11.10.12	48	0
280282	내일 시험을 위해 날 새야하니 지금 자야지	534F444D61737465	11.10.12	34	0
280281	인생은 선택의 연속 [3]	초이스(125.143)	11.10.12	92	0
280280	횽들 C++ 지네릭할때... [4]	ㄴㄴㅇ(116.36)	11.10.12	54	0
280277	홈페이지 배끼면서 공부하는게이인데 +조공 [6]	교복여중고딩	11.10.12	157	0
280276	기아타이거즈가 멸망했슴다 [5]	꼬꼬월드	11.10.12	61	0
280275	delay time 50 이면 몇초임 ? [3]	시개	11.10.12	57	0
280273	프로그래밍 학원중에 비트가 그렇게 甲인가여 [3]	LASTOR	11.10.12	237	0
280272	형들 멀티미디어 질문 !! 쉬운 계산이야 [18]	형들(175.116)	11.10.12	126	0
280269	훈방조치를 위한 떡밥글 [2]	꼬꼬월드	11.10.12	68	0
280268	나 진짜 고소당하면 어떡하지? [8]	꼬꼬월드	11.10.12	128	0
280267	하아횽은 며짤임? [1]	^0^	11.10.12	41	0
280266	너님들 좌욕하는 기분 암?	534F444D61737465	11.10.12	42	0
280265	아 얼혼지 뭔지 짱나니까 [8]	y녀6디리(220.118)	11.10.12	102	0
280264	코딩 하는거 무시하는 [5]	로하로하알로하	11.10.12	85	0
280263	아 글고 또 질문여 질문 [13]	LASTOR	11.10.12	79	0
280262	적어도 내가 아는 보안쪽 파던 애들은 지금 다 서버관리자함 [7]	꼬꼬월드	11.10.12	156	0
280261	학교에서 물리1,2화학생물도 필수로 들어야되는게 짱남 [1]	abbey road	11.10.12	62	0
280260	대기업si는 스펙 뭐필요해? [10]	^0^	11.10.12	190	0
280258	아 수학실력 좆밥인데 큰일났다.. [9]	^0^	11.10.12	121	0
280257	글고 꼬꼬월드님 한번만 봐주세여 [11]	LASTOR	11.10.12	83	0
280256	횽들 정보처리기사 자격증은 어떤내용임?? [5]	없쥐	11.10.12	105	0
280255	이거 짤 줄 아는 사람 있음 ? [2]	시개	11.10.12	67	0
280254	올3등급 맞으면 4년 전액장학금 주는 대학교도 신입으로 대기업si갈 수 [4]	^0^	11.10.12	97	0
280253	As어쩌고님 봐주세요	LASTOR	11.10.12	38	0
280251	팀장님은 아직 정보처리기사 안따셨어요? [18]	꼬꼬월드	11.10.12	201	0
280250	웹개발쪽도 수학 많이 중요하나?? [7]	^0^	11.10.12	121	0
280249	도대체 이게 뭔말인지 모르겠어요 [6]	LASTOR	11.10.12	70	0
280248	printf(“\nPush a Button Switch 이게 뭔말이냐? [4]	시개	11.10.12	90	0
280247	재밌는 이야기가 시작된것같은데,,, [1]	ㅋㄱ(183.96)	11.10.12	38	0
280246	안녕 세상아는 우리 팀장님이 빠질 수가 없지. [1]	Ashenvale(220.90)	11.10.12	67	0
280245	컴공에서 배우는건 공학 수학적 이론60 실제코딩40 정도 [4]	abbey road	11.10.12	119	0
280244	프로그래밍의 시작은 무조건 Hello World라고 생각한다 [3]	꼬꼬월드	11.10.12	108	0
280243	설계할때 [1]	534F444D61737465	11.10.12	38	0
280242	학교다니면 진짜존나 바쁜뎅... [3]	abbey road	11.10.12	71	0
280241	꼬꼬형은 몇년차야? [13]	^0^	11.10.12	107	0
280240	다들 퇴근하셨나?_? [2]	Dawnwalkre	11.10.12	51	0
280239	컴공에서 배우는 것... [8]	534F444D61737465	11.10.12	164	0
280238	횽들 수고하심 [4]	어떡해	11.10.12	47	0
280237	우리 적어도 중앙대 이하급 대졸 뽑는편인데... [6]	꼬꼬월드	11.10.12	171	0
280236	C언어 할 줄 아는사람 이것 좀 봐줘 [3]	시개	11.10.12	112	0
280235	대학생으로서 프로그래밍언어 배운다는건 수치아니냐? [4]	ㅇㅇㅇㅇ(175.204)	11.10.12	125	0
280234	집에[ 전기끊겨서 피ㅣㅆ방와서 프갤중 [1]	^0^	11.10.12	32	0
280233	이야 시발 슬레이트7대박이다 [3]	꿀레(14.33)	11.10.12	229	0
280232	근데 컴공과에서는 뭐 가르침? [23]	꼬꼬월드	11.10.12	248	0
280231	난 그래도 벌레 덕분에 즐겁다. [1]	Ashenvale(220.90)	11.10.12	69	0
280230	일광면 형 글땜에 상처받았다... [3]	얼빠진호랑이	11.10.12	105	0
280229	대학교 문과 졸업해서 학원도 안다니고 개발자로 취직한 사람도 있음.. [6]	꼬꼬월드	11.10.12	176	0
뉴스	“아내가 야한 속옷 입고, 피임도구 챙겨서 등산을 갑니다”	디시트렌드	07.07