Временная сложность программы

Question

 #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);

}

Я получил время работы 0,015 с, когда n = 100000 для вышеуказанной программы. Я также реализовал алгоритм Сита Эратосфена в C и получил время выполнения 0,046 для n = 100000.

Как мой алгоритм работает быстрее, чем алгоритм 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;
}

Answer 1

Есть ряд вещей, которые могут повлиять на ваш результат. Чтобы быть уверенным, нам нужно увидеть код для вашей реализации сита. Кроме того, каково разрешение функции 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;
            }

Answer 2

Какова временная сложность моей вышеуказанной программы ??

Чтобы эмпирически измерить временную сложность вашей программы, вам нужно более одной точки данных. Запустите вашу программу для нескольких значений N, затем составьте график зависимости N от времени. Вы можете сделать это, используя электронную таблицу, GNUplot или миллиметровку и карандаш. Вы также можете использовать программное обеспечение и / или простую старую математику, чтобы найти полиномиальную кривую, которая соответствует вашим данным.

Неэмпирически: много написано (и прочитано на уроках информатики) об анализе вычислительной сложности. Статья в Википедии о теории вычислительной сложности может предоставить некоторые отправные точки для дальнейшего чтения.

Answer 3

Эти времена выполнения слишком малы, чтобы быть значимыми. Разрешение системных часов не соответствует этому уровню.

Что вам нужно сделать, чтобы получить точную информацию о времени, - запустить свой алгоритм в цикле. Повторите это несколько тысяч раз, чтобы увеличить время выполнения хотя бы до секунды, затем вы можете разделить время на количество циклов.

Answer 4

Поведение трудно предсказать, но вы должны принять во внимание, что доступ к памяти недешевый ... вероятно, быстрее просто снова рассчитать его для небольших простых чисел.

Answer 5

Только для вашего времени сложность:

У вас есть внешний цикл итераций ~ LISTMAX и внутренний цикл макс. Перечислите итерации. Это означает, что ваша сложность составляет

O (SQRT (п) * п)

где n = размер списка. На самом деле он немного ниже, поскольку внутренний цикл уменьшает его счет каждый раз и запускается только для каждого неизвестного числа. Но это сложно рассчитать. Поскольку O-нотация предлагает верхнюю границу, O (sqrt (n) * n) должно быть в порядке.

Answer 6

Ваша реализация сита неверна; вот почему это так медленно:

• вы не должны делать это массивом чисел, а массивом флагов (вы все равно можете использовать int в качестве типа данных, но char тоже подойдет)
• Вы не должны использовать сдвиги индекса для массива, но список [i] должен определять, является ли i простым или нет (а не является ли i + 2 простым)
• вы должны начать устранение с i = 2
• с этими изменениями вы должны следовать совету ИНФОРМАЦИИ 1800 и отменить все кратные i с циклом, который идет с шагом i, а не с шагом 1