amm7931   7년 전

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

int main(void)
{
 int N,i,x,t,sum=0;
 scanf("%d",&N);
 int *A=(int*)malloc(sizeof(int)*N);
 for(i=0;i<N;i++)
  scanf("%d",&A[i]);
 for(t=0;t<N-1;t++)
 {
  for(i=0;i<N-1;i++)
  {
   if(A[i]>A[i+1])
   {
    x= A[i];
    A[i]=A[i+1];
    A[i+1]=x;
    sum++;
   }
  }
 }
 printf("%d\n",sum);
 return 0;

}

왜 시간초과 나오는건가요 도저히 모

hjroh0315   7년 전

250000000000번 반복하면 1초 안에 불가능해요

amm7931   7년 전

죄송하지만 구체적으로 설명해주실 수 있을까요??

hjroh0315   7년 전

N이 최대 500000이고 버블정렬의 시간복잡도는 O(N2)입니다.즉 N2번 반복한다는 것이지요. 그런데 5000002 즉 250000000000번 반복하면 1초를 넘는 것이 대부분입니다.

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