Обозначение Big-O - вложенные зависимые циклы - PullRequest
1 голос
/ 29 марта 2019

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

В самом внутреннем цикле, который удаляет +, есть изменение / чтение, которое я могу внести в самый внутренний цикл.1-1, но это не должно быть фактором в моих вычислениях.

Я понимаю, что сложность вложенных циклов умножается.Теперь у меня есть конец вычисления, и я не знаю, должен ли я, поскольку в цикле n-2 раза, заменить i в результате на (n-2)?Тот же вопрос о среднем цикле, должен ли я заменить j на (k - m * i + m)?

Поскольку я пока не могу публиковать изображения, я поставлю здесь ссылку на нее, а также скопирую и вставлю ее ниже(for-loop и мои вычисления):

        for(int i = 1; i < n; i++){
            for(int j = ((m+1)*(i-1)) + 1; j < k; j++){
                for(int h = (m+1)*(i-1); h < (j-m+1)-1; h++){ 
                }
            }
        }


Inner most loop    
  (j-m-1 - 1) - ((m+1)*(i-1))     =
= (j-m-1 - 1) - (m*i - m + i - 1) =
= j - m - 1 - 1 - m*i + m - i + 1 =
= j - m*i - 1

2º Inner most loop
  (k - 1) - ((m+1)*(i-1))     =
= (k - 1) - (m*i - m + i - 1) =
= k - 1 - m*i + m - i + 1     =
= k - m*i + m                 

Outer loop
  n - 1 - 1 = 
= n - 2

Result
  (j - m*i) * (k - m*i + m) * (n)                     =
= (j*k - j*m*i + j*m - m*i*k + (m*i)^2 - (m^2)*i) * n

Изображение: https://imgur.com/a/40eIlDj

Спасибо за внимание

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...