Блог

Я работаю над поиском точной и большой временной сложности следующего тройного вложенного цикла for и смущен, если я делаю это правильно.

 for (int i=1; i<=n; i  )
   for (int j=i; j<=n; j  )
      for (int k=i; k<j; k  )
          sum  ;
  

Я знаю, что внешний цикл выполняется n раз. Затем второй цикл выполняется разное количество раз каждый раз, поскольку он начинается с i:

n (n-1) (n-2) … 2 1.

Но, поскольку мы заботимся только о наихудшем сценарии (который будет, когда i = n), тогда второй цикл будет выполняться n-n раз, поскольку он начнется при i = n . Это, конечно, не имеет смысла, но именно здесь я застрял. Я запустил код для этого и нашел первые четыре элемента последовательности: S = 0 1 4 10 … ( не уверен насчет всего остального).

Извините, если это не имеет смысла, но любая помощь была бы очень признательна!

Важно знать, что все арифметические ряды, подобные 1 2 3 ... n O(n^2) . Таким образом, вы получаете три вложенных цикла, каждый из O(n) которых включен, поэтому общая временная сложность равна O(n^3) или, если быть более точным, Θ(n^3) .

Обратите внимание, что здесь нет «наихудшего» или «наилучшего случая», поскольку количество шагов зависит только от n и ничего больше. Сравните это, например, с алгоритмами сортировки, где количество шагов может зависеть не только от количества n элементов, подлежащих сортировке, но и от значений элементов и их конкретного порядка.