dexaboud3   8년 전

위에 수를 버블로 정렬한다음

아래줄의 수와 이진검색을 통해서 했는데 시간초과가 뜨네요.....

91%에서 시간초과가 뜨는데.... 더 시간을 줄일수 있는 방법이 있을까요...?

알려주세요 .. ㅠㅠ

#include<stdio.h>
#include<stdlib.h>

void bubble(int arr[],int len){
int i,j;
int buf;

for(i=0;i<len-1;i++){
for(j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){
buf=arr[j];
arr[j]=arr[j+1];
arr[j+1]=buf;
}
}
}
}

int binsearch(int s[],int len,int key){
int mid,low,high;
int location=-1;
low=0;high=len-1;

while(high>=low && location==(-1)){
mid=(low+high)/2;
if(s[mid]==key) location=mid;
else if(s[mid]>key) high=mid-1;
else low=mid+1;
}
if(location==(-1)) return 0;
else return 1;
}

int main(void){
int alen,blen;
int*as;int*bs;
int i;
int ch;

scanf("%d",&alen);
as=(int*)malloc(sizeof(int)*alen);
for(i=0;i<alen;i++) scanf("%d",&as[i]);

bubble(as,alen);

scanf("%d",&blen);
for(i=0;i<blen;i++){
scanf("%d",&ch);
printf("%d\n",binsearch(as,alen,ch));
}
return 0;
}

kesakiyo   8년 전

버블정렬을 하는데 시간복잡도는 O(n^2) 입니다.

해당 문제에서 n이 10만이기 때문에 n^2은 100억정도 되고

약 10억의 연산에 1초정도 걸린다고 하면 10초의 시간이 걸리게 되므로 시간초과를 받게 됩니다.


좀더 효율적인 정렬 알고리즘으로는 평균시간복잡도가 O(nlogn) 인 퀵소트와

최악의 시간복잡도가 O(nlogn) 인 힙소트, 머지소트 등이 있습니다.


c++에서 제공해주는 라이브러리 함수로 [a, b) 구간을 정렬해주는 sort 함수가 있는데

http://www.cplusplus.com/reference/algorithm/sort/...

위에 래퍼런스를 참고해 보는방법도 좋은것 같습니다.


혹시 시간복잡도가 무엇인지 모르겠다 하신다면 시간복잡도를 공부해 보시는 것도 좋다고 생각합니다.


마지막으로 소스를 복붙하실때는 본문말고 소스코드 란에 첨부해 주신다면 더욱 보기가 편합니다.

dexaboud3   8년 전

감사합니다!! 해결했어요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.