Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 82

Пусть A [1,…, n] будет массивом, хранящим бит (1 или 0) в каждом местоположении, а f (m) является функцией, сложность времени которой равна θ (m). Рассмотрим следующий фрагмент программы, написанный на C-подобном языке:

counter = 0;

for (i = 1; i < = n; i++)

      if (A[i] == 1) 

         counter++;

      else {

         f(counter); 

         counter = 0;

      }

}

Сложность этого фрагмента программы
(A) Ω (n 2 )
(B) Ω (nlog n) и O (n 2 )
(C) θ (n)
(D) O (n)

Ответ: (с)
Объяснение: Обратите внимание, что внутри условия else сначала вызывается f (), затем счетчик устанавливается в 0.

Рассмотрим следующие случаи:

a) All 1s in A[]: Time taken is Θ(n) as
                  only counter++ is executed n times.

b) All 0s in A[]: Time taken is Θ(n) as
                  only f(0) is called n times

c) Half 1s, then half 0s: Time taken is  Θ(n) as
                  only f(n/2) is called once.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2004 | Вопрос 82

0.00 (0%) 0 votes