Big-O цикла while с вложенным if - PullRequest
Новая
       7

Big-O цикла while с вложенным if

0 голосов
/ 26 января 2019

У меня есть этот алгоритм, и я пытаюсь вычислить его сложность. 

A = {{B_1}, {B_2}, {B_3}, ..., {B_n}}
t_n = 0   //for every set in A
while A != empty
   Calculate f(t_n) for each element in A using t_n. 
   n' = argmin(A)  //n' is the element (set) in A with smallest f(t_n)
   t_n' = t_n' + 1
   if (t_n' == Constant)
       B_n' = B_n' - {k}     //k is an element in B_n'
       if(B_n' == empty)
           A = A - {B_n'}

A является набором, и если условия (t_n' == Constant) и if(B_n' == empty) равны true , мы удаляем элемент (набор) из набора A до A пусто. Предположим, что вычисление f(t_n) занимает постоянное время.

Если каждый элемент (набор) в A имеет одинаковый размер, можем ли мы сказать, что сложность равна O(|A|*|B_n|)? Как насчет того, если элементы (наборы) в A имеют разные размеры?

...