Блог

У меня есть следующая последовательность циклов.

   TripleLoop(int n)
   for i <- 1 to n
       for j <- 1 to n
          for k <- j to n 
   do num <- j   i
   return num
  

Я знаю, что два внешних цикла выполняются «n» раз.
Таким образом, мы имеем n * n = n ^ 2 для двух внешних циклов.
Однако третий внутренний цикл зависит от переменной «j».

Как мне начать решать эти типы вложенных зависимых циклов for? Я не уверен, следует ли мне умножать или добавлять третий внутренний цикл к двум внешним циклам.

Кто-нибудь может мне здесь помочь?

Ну, внутренний цикл (тот, у которого k в качестве итератора) выполняется n-j 1 раз, поскольку он начинается с j и заканчивается на n .

Общее количество шагов, выполняемых таким образом средним for циклом, равно сумме шагов за итерацию для j , так что это означает, что общее количество раз, когда мы запускаем тело внутреннего цикла for, равно:

  n
---
                  n * (n   1)
/    n - j   1  = -------------
---                    2
j=1
  

итак, после одной итерации внешнего цикла (с i в качестве итератора) у нас есть n*(n 1)/2 шаги.

Таким образом, в общей сложности наш алгоритм будет запускать тело внутреннего цикла в общей сложности n * n * (n 1)/2 раз. Поскольку внешний цикл выполняется n раз, и количество шагов в теле этого цикла не зависит от значения i самого цикла.

Если мы рассматриваем num <- j 1 часть для выполнения в постоянное время (ну, строго говоря, суммирование огромных чисел не может быть выполнено в постоянное время), то это, таким образом, алгоритм O (n³).