Анализ временной сложности

Question

Я пытаюсь вычислить и проанализировать это здесь.

public static long double_for_loop(int z){
      long result = 0;
      for(int i =0; i<z;i++){
         for(int j =i + 1; j>i; j--){
            result +=(i*j);
         }
      }
    return result;
   }

Нужна помощь в решении временной сложности для каждой последовательности операторов. Я хочу знать, как это решить.

Answer 1

Внутренний l oop выполнит свою первую итерацию с j=i+1, затем j будет уменьшаться и условие не выполняется. Следовательно, он будет выполняться в Θ(1). Внешний l oop будет выполняться z раз, поэтому для double for и самой функции временная сложность будет Θ(z)

Answer 2

Для z = 4 процесс (внутренний l oop) выглядит следующим образом:

I = 0, J выполняется за 1 шаг ==> O (1) , постоянное время

I = 1, J выполняется за 1 шаг ==> O (1) , a постоянное время

I = 2, J выполняется за 1 шаг ==> O (1) , постоянное время

I = 3, J выполняется за 1 шаг ==> O (1) , постоянное время

Итак, у вас есть O (1) , которое a постоянное время независимо от того, насколько велико значение Z . Некоторые люди, которых я вижу, пишут это как O (4), но обычно мы просто пишем это как O (1) . Обычно O (C1) рассматривается как O (C2) для любых положительных целых констант C1 и C2. Так что не имеет значения, если вы просто напишете это как O (1) . Дело в C значение не зависит от ввода Z размер. Сценарий будет другим, если он будет J = Z вместо J = I + 1 . В этом случае внутренний l oop оказывается линейным O (Z) потому что это зависит от Z .

Итак, в целом вы получаете O (Z) для внешней * O (1) для внутренней части, которая представляет собой O (Z) линейное время сложность.