[컴퓨터_인터넷] C언어 시간복잡도(big-O) 좀 알려주세요.
2009.10.26 22:25
4,433
3
0
본문
어째 네이버에다 내공 100 올려논지가 몇주가 되도록 답변 달릴 생각을 않하는군요;;;
당장 시험이 얼마 않남았는데, 어째 과에 풀줄 아는 사람이 없어요. [머엉]
int Maxsubsum(A[], LB, RB)
{
if (LB == RB) {
if(A[LB] > 0) return A[LB];
else return 0;
}
Center = (LB + RB) / 2;
Max1 = Maxsubsum(A, LB, Center);
Max2 = Maxsubsum(A, Center+1, RB);
for(i = Center ; i >= LB ; i--)
Max31 += A[i];
for(i = Center+1 ; i <= RB ; i++)
Max32 += A[i];
return Max_3(Max1, Max2,(Max31+Max32));
}
{
if (LB == RB) {
if(A[LB] > 0) return A[LB];
else return 0;
}
Center = (LB + RB) / 2;
Max1 = Maxsubsum(A, LB, Center);
Max2 = Maxsubsum(A, Center+1, RB);
for(i = Center ; i >= LB ; i--)
Max31 += A[i];
for(i = Center+1 ; i <= RB ; i++)
Max32 += A[i];
return Max_3(Max1, Max2,(Max31+Max32));
}
(단, MAX_3()은 3개의 값 중에서 가장 큰 값을 구하는 O(1)인 함수임)
이 함수의 시간복잡도 big-O 갖다가 풀라는건데요.
애초에 이게 뭘 구하는 함순지도 정확히 모르지라. [야임마!]
알려주시면 정말 감사하겠습니다. [굽신굽신]
- 1.27Kbytes
0
로그인 후 추천 또는 비추천하실 수 있습니다.
최신글이 없습니다.
최신글이 없습니다.
전체 12 건 - 1 페이지
댓글목록 3
Estas님의 댓글
- Estas님의 홈
- 전체게시물
- 홈페이지
- 아이디로 검색
2009.10.26 23:43저게 뭐하는 물건인지는 대충 순서도 그려가며 해 보면 될 듯 하지만... 시간 복잡도가 뭔지 몰라서 패스 -_-;
까만도마뱀님의 댓글
- 까만도마뱀님의 홈
- 전체게시물
- 아이디로 검색
2009.10.27 09:59간단하게 이야기해서 -1,3,4,2,-6,6 요런배열이 들어왔을때, 3,4,2의 합인 9를 구하는 함수입니다.
근데 알고리즘 자체가 에러가 있는듯합니다.. 무조건 반씩 짜르면 특정짓는 범위가 1/2,1/4,1/8등등으로 제한됩니다..
bigO를 구하는건 좀 어렵긴한데 결론만 이야기해드리면 O(NlogN) 의 시간복잡도를 가지는 함수입니다.
전체 데이터를 logN의 횟수만큼 읽게 됩니다. quick sort랑 비슷한 알고리즘으로 동작을 하는군요.
페일미스트님의 댓글
- 페일미스트님의 홈
- 전체게시물
- 홈페이지
- 아이디로 검색
2009.10.28 01:50Big-O는 worst-case아니었나요?
저는 O(n^2)라고 생각했는데 말이지요;;