Временная сложность алгоритма сортировки - PullRequest
Новая
       8

Временная сложность алгоритма сортировки

4 голосов
/ 11 апреля 2010

Две программы, приведенные ниже, получают n целых чисел из файла и вычисляют сумму умноженных на число целых чисел q (количество вопросов). Я думаю, что у верхней программы сложность по времени хуже, чем у нижней, но у меня возникают проблемы с вычислением временной сложности этих двух алгоритмов. 

[input sample]
5 3
5 4 3 2 1
2 3
3 4
2 4

[output sample]
7
5
9

Программа 1: 

#include <stdio.h>

FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");

int n,q,a,b,sum;
int data[1000];

int main()
    int i,j;
    fscanf(in,"%d%d",&n,&q);
    for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
    for i=0;i<q;i++)
    {
        fscanf(in,"%d%d",&a,&b);
        sum=0;
        for(j=a;j<=b;j++) sum+=data[j];
        fprintf(out,"%d\n",sum);
    }
    return 0;
}

Программа 2: 

#include <stdio.h>

FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");

int n,q,a,b;
int data[1000];
int sum[1000];

int main()
{
    int i,j;
    fscanf(in,"%d%d",&n,&q);
    for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+data[i];
    for(i=0;i<q;i++)
    {
        fscanf(in,"%d%d",&a,&b);
        fprintf(out,"%d\n",sum[b]-sum[a-1]);
    }
    return 0;
}

Приведенные ниже программы получают n целых чисел от 1 до m и сортируют их. Опять же, я не могу рассчитать сложность времени. 

[input sample]
5 5
2 1 3 4 5

[output sample]
1 2 3 4 5

Программа: 

#include <stdio.h>
FILE *in=fopen("input.txt","r")
FILE *out=fopen("output.txt","w")

int n,m;
int data[1000];
int count[1000];

int main()
{
    int i,j;
    fscanf(in,"%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        fscanf(in,"%d",&data[i]);
        count[data[i]]++
    }
    for(i=1;i<=m;i++)
    {
        for(j=0;j<count[i];j++) fprintf(out,"%d ",i);
    }
    return 0;
}

Забавно (или нет), что я не могу рассчитать временную сложность своих собственных алгоритмов, но у меня есть страсть к изучению, поэтому, пожалуйста, гуру программирования, помогите мне!

1 Ответ

3 голосов
/ 11 апреля 2010

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

В вашей первой программе у вас есть один цикл, который занимает O (n) время, за которым следует цикл, который занимает O (q * (ba)) время ... мне не совсем ясно, что представляют собой b и a ... но если вы можете связать ba (скажем, вы знаете, что ba

Во второй программе у вас есть два цикла, каждый из которых занимает время O (n), а затем цикл, который занимает время O (q). Таким образом, общее время выполнения O (n + q). Обратите внимание, что если один термин доминирует над другим, вы можете отбросить термин, который меньше. Даже не зная значения (b-a), уже очевидно, что это лучше, чем первое.

В третьей программе общее время выполнения равно O (n + m), потому что у вас есть один цикл, который занимает время O (n), а затем цикл, который занимает время O (m). Если вы знаете, что m

Я также должен отметить, что даже если цикл выполняется более одного раза, но он выполняется фиксированное число раз (например, в программе 2 у вас есть два цикла, которые занимают O (n) времени), он не ' t влияет на сложность времени, потому что O (2n) совпадает с O (n); Другими словами, постоянные факторы не имеют значения при анализе сложности. Кроме того, если у вас есть внутренний цикл, который изменяется с точки зрения количества раз его выполнения, если вы выполняете анализ сложности "наихудшего случая", вам нужно знать только худшее возможное значение, которое он может иметь.

Например, рассмотрим следующий цикл: 

for (int i = 0; i < n; i++ ){
   for (int j = i+1; j < n; j++ ){
       // something taking O(1) time
   }
}

Вышеприведенный цикл занимает время O (n ^ 2), хотя не все внутренние циклы занимают время O (n).

Я также хотел бы добавить, что вам лучше работать с форматированием вашей программы. Хотя фигурные скобки не являются строго обязательными, если в условии if / for / while есть только один оператор в теле, в любом случае гораздо удобнее использовать фигурные скобки и использовать новую строку. Например, это будет намного более читабельным, если вы напишите: 

for (int i=1; i<=n; i++) {
    sum[i]=sum[i-1]+data[i];
}

Чем писать это как for (i=1; i<=n; i++) sum[i]=sum[i-1]+data[i];. Кроме того, я должен отметить, что даже если вы пометили этот вопрос как C ++, вы используете C-подобный код ... в C ++ вы можете объявить переменные при инициализации цикла for (я предлагаю вам сделать это). Кроме того, в C ++ библиотека iostreams ( std :: cin , std :: cout , std :: fstream , std :: ostringstream , std :: istringstream и т. д.) предпочтительнее объектов C FILE *.

Вам также может быть интересен следующий ресурс:

...