Я упрощаю расчет сложности - PullRequest
Новая
       13

Я упрощаю расчет сложности

0 голосов
/ 14 сентября 2018

Я просто пытаюсь вычислить сложность некоторых фрагментов программы, но я беспокоюсь, что делаю вещи слишком простыми.Если я положу свои фрагменты и ответы вниз, вы можете сказать мне, если я делаю что-то не так с этим?

(a) 

sum = 0;
for (i = 0;i < n;i++)
    sum++;

ОТВЕТ: n, только один для цикла

(b) 

sum = 0;
for (i = 0;i < n;i++)
    for (k = 0;k < n*n;k++)
        sum++;

ОТВЕТ: n ^ 2 из-за вложенного цикла, хотя мне интересно, если n * n во вложенном цикле делает его n ^ 3

(c) 

sum = 0;
for (i = 0;i < n;i++)
    for (k = 0;k < i;k++)
        sum++;

ОТВЕТ: n ^ 2

(d) 

sum = 0;
for (i = 0;i < n;i++)
    for (k = 0;k < i*i;k++)
        sum++;

ОТВЕТ: n ^ 2, но меня беспокоит то же, что и b

(e) 

sum= 0;
for (i = 0;i < n;i++)
    for (k = i;k < n;k++)
        sum++;

ОТВЕТ: n ^ 2

1 Ответ

0 голосов
/ 18 сентября 2018

Поскольку во всех ваших примерах основная операция - sum++, мы обязаны подсчитывать, сколько раз эта базовая операция выполняется.

Кроме того, во всех случаях есть операция i++, это также считается, как и k++.Наконец, эти счетчики должны сравниваться с их пределами на каждом этапе, и мы также должны принимать во внимание эти сравнения.Теперь эти дополнительные операции не меняют количество итераций;они просто делают каждую итерацию дороже.Например,

(a) 

sum = 0;
for (i = 0;i < n;i++)
  sum++;

повторяется n раз: i++, sum++ и i<n, все из которых дают 3n операций аналогичной сложности,Вот почему общая сложность составляет O(n).

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

Второй пример 

sum = 0;
for (i = 0;i < n;i++)
  for (k = 0;k < n*n;k++)
    sum++;

повторяет n время операции 

  for (k = 0;k < n*n;k++)
    sum++;

Из-за предыдущего случая эта операция имеет сложность O(n*n), как здесьограничение составляет n*n, а не n.Таким образом, общая сложность составляет O(n*n*n).

Третий пример аналогичен, за исключением того, что на этот раз выполняемая операция n раз равна 

for (k = 0;k < i;k++)
    sum++;

, сложность которой изменяется сi.Следовательно, вместо умножения на n мы должны суммировать n разных вещей: 

O(1) + O(2) + ... + O(n)

, и поскольку постоянный коэффициент, неявный в O, всегда одинаков (= число увеличиваемых переменныхили сравнивать на каждом элементарном этапе), мы можем переписать его как 

O(1 + 2 + ... + n) = O(n(n+1)/2) = O(n*n)

Другие примеры похожи в том, что их можно проанализировать, следуя этим же идеям.

...