프로그램의 시간 복잡도

StackOverflow https://stackoverflow.com/questions/1353252

문제 

 #include<stdio.h>
 #include<time.h>

 int main()

  {

    clock_t start;
    double d;
    long int n,i,j;
    scanf("%ld",&n);
    n=100000;
    j=2;
    start=clock();
    printf("\n%ld",j);

       for(j=3;j<=n;j+=2)
       {
          for(i=3;i*i<=j;i+=2)

          if(j%i==0)
            break;

           if(i*i>j)
          printf("\n%ld",j);

        }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;
    printf("\n%f",d);

}

위 프로그램의 경우 n=100000일 때 0.015초의 실행 시간을 얻었습니다.또한 C에서 Sieve of Eratosthenes 알고리즘을 구현했으며 n=100000에 대해 0.046의 실행 시간을 얻었습니다.

위의 알고리즘이 내가 구현한 Sieve의 알고리즘보다 얼마나 빠른가요?

위 프로그램의 시간 복잡도는 얼마입니까??

내 체의 구현

 #define LISTSIZE 100000    //Number of integers to sieve<br>
 #include <stdio.h>
 #include <math.h>
 #include <time.h>

int main()
{   


    clock_t start;
    double d;
    long int list[LISTSIZE],i,j;
    int listMax = (int)sqrt(LISTSIZE), primeEstimate = (int)(LISTSIZE/log(LISTSIZE));

    for(int i=0; i < LISTSIZE; i++)
        list[i] = i+2;
    start=clock();

    for(i=0; i < listMax; i++)
    {
        //If the entry has been set to 0 ('removed'), skip it
        if(list[i] > 0)
        {
            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                if((list[j] % list[i]) == 0)
                    list[j] = 0;
            }
        }
    }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;

    //Output the primes
    int primesFound = 0;
    for(int i=0; i < LISTSIZE; i++)
    {
        if(list[i] > 0)
        {
            primesFound++;

            printf("%ld\n", list[i]);
        }
    }
    printf("\n%f",d);
    return 0;
}
도움이 되었습니까?

해결책

결과에 영향을 줄 수있는 많은 것들이 있습니다. 확실히, 우리는 당신의 체 구현을위한 코드를 봐야합니다. 또한의 해상도는 무엇입니까? clock 컴퓨터에서 기능? 구현이 밀리 초 수준에서 높은 수준의 정확도를 허용하지 않으면 결과가 측정의 오류 마진 내에있을 수 있습니다.

문제가 여기에 있다고 생각합니다.

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                    if((list[j] % list[i]) == 0)
                            list[j] = 0;
            }

이것은 소수의 모든 배수를 제거하는 가난한 방법입니다. 구축 된 곱셈 연산자를 사용하여 배수를 제거하지 않겠습니까? 이 버전은 훨씬 더 빠릅니다.

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = list[i]; j < LISTSIZE; j+=list[i])
            {
              list[j] = 0;
            }

다른 팁

위의 프로그램의 시간 복잡성은 얼마입니까?

프로그램의 시간 복잡성을 경험적으로 측정하려면 둘 이상의 데이터 포인트가 필요합니다. N의 여러 값에 대한 프로그램을 실행 한 다음 N과 시간의 그래프를 만듭니다. 스프레드 시트, gnuplot 또는 그래프 용지 및 연필을 사용하여이를 수행 할 수 있습니다. 또한 소프트웨어 및/또는 일반 오래된 수학을 사용하여 데이터에 맞는 다항식 곡선을 찾을 수 있습니다.

비 홍보 적으로 : 계산 복잡성 분석에 관한 많은 것이 쓰여졌다 (컴퓨터 과학 수업에서 강의). 위키 백과 기사 계산 복잡성 이론 추가 읽기를위한 몇 가지 출발점을 제공 할 수 있습니다.

체의 구현이 잘못되었습니다. 그것이 너무 느린 이유입니다.

  • 숫자 배열을 만들지 말고 플래그 배열을 만들어야합니다 (int를 데이터 유형으로 사용할 수도 있지만 char도 마찬가지입니다).
  • 배열에 인덱스 이동을 사용해서는 안되지만 [i]는 내가 프라임인지 아닌지를 결정해야합니다 (I+2가 프라임인지 여부가 아님).
  • i = 2로 제거를 시작해야합니다
  • 이러한 수정을 통해 1800 정보의 조언을 따르고 1의 단계가 아닌 I의 단계로 들어가는 루프로 I의 모든 배수를 취소해야합니다.

시간 복잡성을 위해서만 :

~ listmax 반복의 외부 루프와 최대 내부 루프가 있습니다. ListSize 반복. 이것은 당신의 복잡성이 있음을 의미합니다

o (sqrt (n)*n)

여기서 n = listsize. 내부 루프가 각 시간을 계산하고 알 수없는 숫자에 대해서만 실행되기 때문에 실제로는 약간 낮습니다. 그러나 그것은 계산하기가 어렵습니다. O- 반드시는 상한을 제공하므로 O (sqrt (n)*n)은 괜찮습니다.

행동은 예측하기 어렵지만 메모리에 액세스하는 것이 저렴하지 않다는 것을 고려해야합니다. 작은 프라임에 대해 다시 계산하는 것이 더 빠릅니다.

실행 시간이 너무 짧아서 의미가 없습니다.시스템 클럭 해상도는 그런 수준에는 정확하지 않습니다.

정확한 타이밍 정보를 얻기 위해 해야 할 일은 알고리즘을 루프에서 실행하는 것입니다.이를 수천 번 반복하여 실행 시간을 최소 1초로 만든 다음 시간을 루프 수로 나눌 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top