Я не понимаю, как рассчитывается сложность времени для этого алгоритма - PullRequest
Новая
       10

Я не понимаю, как рассчитывается сложность времени для этого алгоритма

0 голосов
/ 14 декабря 2018 
int j=0;
for (int i=0; i<N; i++) 
{
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1; 
}

Говорят, что этот код имеет временную сложность O (n), но я не совсем понял.Внутренний цикл выполняется N раз, а внешний также должен быть N раз?Может быть из-за j = 0;за пределами цикла, который заставляет его работать только N раз?

Но даже если он будет выполняться только N раз во внутреннем цикле, проверка статов должна выполняться также N раз, что должно привести к общей сложности временив O (n ^ 2)?

1 Ответ

0 голосов
/ 14 декабря 2018

Причина, по которой это O (n) , заключается в том, что j это , а не , установленное обратно в 0 в теле цикла for.

Действительно, если мы посмотрим на тело цикла for, мы увидим: 

while ( (j<N-1) && (A[i]-A[j] > D) )
    j++;

Это означает, что j++ выполнено не более n-1 раз, так как если j успешно N-1 раз, то первое ограничение не выполняется.

Если мы посмотрим на весь цикл for, мы увидим: 

int j=0;
for (int i=0; i<N; i++) {
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1;
}

Понятно, что тело цикла for повторяется n раз, поскольку мы устанавливаем i в i=0 и останавливаемся, когда i >= N, и каждыйитерацию мы увеличиваем i.

Теперь в зависимости от значений в A мы будем увеличивать или не увеличивать j (несколько раз) в теле цикла for.Но независимо от того, сколько раз это делается за одну итерацию, в конце цикла for, j++ выполняется не более n раз, по той причине, о которой мы упоминали выше.

Условие в цикле while выполняется O (n) (а точнее самое большее 2 × n-1 раз), а также: оно выполняется один раз каждый размы вводим тело цикла for и каждый раз после выполнения команды j++, но так как оба O (n) , это делается не более O (n +)n) , таким образом, O (n) раз.

Условие if в цикле for выполняется n раз: один раз за итерациюfor цикл, и снова O (n) .

Так что это действительно означает, что все "основные инструкции" (j++, i = 0, j = 0, j < N-1и т. д.) все выполняются либо постоянное число раз O (1) , либо линейное число раз O (n) , следовательно, алгоритм равен O (п) .

...