Временная сложность функции с функцией * функция в цикле - PullRequest
Новая
       6

Временная сложность функции с функцией * функция в цикле

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

Можете ли вы помочь мне, пожалуйста, чтобы найти сложность следующей функции: 

proc (int n) 
{
 for (i=0 ; i<n ; i++)
 {
   x = g(n)+f(n) ;
   for (j=0 ; j<n ; j++)
    {
      y=h(j)*g(j) ;
    }
  }
return x+y ;
}

С f = O (n ^ 2), g = O (n), h = Θ (log (n)).

Вещи, в которых я не уверен:

  1. В чем сложность "y = h (j) * g (j)", как по мне n * log(п)?
  2. Есть ли разница в сложности, если в цикле "y = h (j) * g (j)" или просто "h (j) * g (j)"?
  3. Правильно ли, что сложность "x = g (n) + f (n)" равна n + n ^ 2?

Спасибо!

Ответы [ 2 ]

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

Сложность внутреннего цикла (сумма h*g)

Поскольку h(j) = Θ(log(j)) и g(j) = O(j), сложность h(j).g(j) равна O(j.log(j)), то есть <= K.j.log(j) для K> 0. Следовательно, внутренний цикл дает 

   K.(1.log(1) + 2.log(2) + ... + (n-1).log(n-1))
<= K'.n^2.log(n)

Для правильно выбранной константы K' и внутренний цикл дает сложность O(n^2.log(n)).

Сложность g + f
g = O(n) и f = O(n^2), поэтому сложность f + g равна O(n^2).

Общая сложность
A: Сумма n условий O(n^2) для f+g дает O(n^3).
B: Сумма условий j^2log(j) для 0 <= j < n дает O(n^3.log(n)).

Поэтому сложность вашего метода составляет O(n^3.log(n)).

0 голосов
/ 18 ноября 2018 
Big O of x = O(n^2)
Big O of y = O(n log(n))

Теперь, чтобы вычислить Big O всего алгоритма, нам нужно взглянуть на самый внутренний цикл.И в этом случае самый внутренний цикл содержится в y = h (j) * g (j).Большое О можно вычислить, начиная с самого низкого и двигаясь вверх.Большое О для x будет добавлено без умножения, потому что оно находится на том же уровне, что и внутренний цикл for. 

Big O = O(n log(n)) * O(n) * O(n) + O(n^2)
It can be written as:
Big O = O ((n log(n) * n * n) + (n * n^2))
Big O = O((n^3 log(n) + n^3)
Neglecting smaller terms would give us:
Big O = O(n^3 log(n))
...