функция суммирования доказать, что это большая ой и большая тета - PullRequest
Новая
       62

функция суммирования доказать, что это большая ой и большая тета

0 голосов
/ 04 октября 2019

Я не понимаю, как решить задачу суммирования, доказывающую, что это большое число n ^ 4 и большое число омега n ^ 4.

Проблема в следующем: 

f(n) = Σ(i=1 to n) Σ(j=1 to i) Σ(k=1 to j) of k

Я написал код на C ++ для того, что, как мне кажется, говорит суммирование. 

for(int i = 1; i <=n; i++)
  for(int j = 1; j <= i; j++)
    for (int k = 1; k<= j; k++)
      something bigoh(1)

Я знаю, что мне нужно доказать, что это большая и большая омега n ^ 4

1 Ответ

1 голос
/ 04 октября 2019

Ваш код не отражает сумму, поскольку последняя часть формулы суммирования равна k , в то время как ваш код предполагает постоянную для внутренней части («что-то bigoh (1)»). Код должен быть: 

sum = 0
for(int i = 1; i <=n; i++)
  for(int j = 1; j <= i; j++)
    for (int k = 1; k <= j; k++)
      for (int m = 1; m <= k; m++)
         sum++

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

sum += k

... но, написав его таким образом, вы можете перевести проблемусколько раз sum++ выполняется в коде.

Представьте, что у вас есть массив значений 1,2, ... n , и что вы должны выбрать из него четыре числа(позволяет снова выбрать тот же номер), но порядок выбора не важен, тогда вы можете выбрать: 

 1, 1, 1, 1
 2, 1, 1, 1
 2, 2, 1, 1
 2, 2, 2, 1
 2, 2, 2, 2
 3, 1, 1, 1
 3, 2, 1, 1
 ...

... и т. д. Вы не будете считать {1, 2, 1, 1}, поскольку вы уже сосчитали {2, 1, 1, 1} - порядок не различен. Поэтому мы считаем только то, где выбранные числа расположены в порядке возрастания.

Теперь обратите внимание, как четыре вложенных цикла в этом (исправленном) коде делают именно это: они повторяют такие комбинации, избегая подсчета набора дважды. (сохраняя i> = j> = k> = m ).

Таким образом, учитывая, что внутренняя задача имеет постоянную сложность по времени, эта проблема сводится к следующему: сколько таких комбинаций существует?

Это комбинация с повторениями . Это обозначается как C ((n, m)) , где в нашем случае m = 4 , поэтому мы считаем число 4-множественных подмножеств , C ((n, 4)) ("n multihoose 4"). Это число эквивалентно

n (n + 1) (n + 2) (n + 3) / 4!

Это, очевидно, O (n 4 ) .

Невозможно выполнить меньшее (или большее количество) исполнений внутренней части вложенных циклов, поэтому это также нижняя граница: Ω (n * 1046)* 4 )

...