Рубрики

Алгоритмы | Анализ алгоритмов | вопрос 2

Алгоритмы Задачи

Какова временная сложность fun ()?

int fun(int n)

{

  int count = 0;

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

     for (int j = i; j > 0; j--)

        count = count + 1;

  return count;

} 

(A) Тета (n)
(B) Тета (n ^ 2)
(С) Тета (n * Logn)
(D) Тета (nLognLogn)

Ответ: (Б)
Объяснение: Сложность времени может быть рассчитана путем подсчета числа раз выполнения выражения «count = count + 1;». Выражение выполняется 0 + 1 + 2 + 3 + 4 +…. + (n-1) раз.

Временная сложность = Тета (0 + 1 + 2 + 3 + .. + n-1) = Тета (n * (n-1) / 2) = Тета (n 2 )
Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Анализ алгоритмов | вопрос 2

0.00 (0%) 0 votes