Какова будет временная сложность следующего алгоритма?

Question

for(i=0;i< m; i++)
{

   for(j=i+1; j < m; j++)
   {

      for(k=0; k < n;k++)
      {
         for(l=0;l< n;l++)
         {if(condition) do something}
      }
   }

} 

Answer 1

Подробнее:

Два первых цикла приведут к (m-1) + (m-2) + (m-3) + ... + 1 повторениям, что равно m *(м-1) / 2.Что касается вторых двух циклов, они в основном выполняются от 0 до n-1, поэтому им нужно n ^ 2 итерации.

Поскольку вы не знаете, будет ли выполнено условие или нет, вы берете наихудший случай, что всегда выполняется.

Тогда число итераций будет:

m * (m + 1) / 2 * n ^ 2 * NumberOfIterations (Something)

В обозначениях O константы и более низкие степени не обязательны, поэтому сложность такова:

O (m ^ 2 * n ^ 2) * O (Something)

Answer 2

for(i=0;i< m; i++)
{  
   for(j=i+1; j < m; j++)
   {

Внутренний цикл будет выполняться ((m-1) + (m-2) + ... 1) раз

= 1 + 2 + 3 + ...m-1 
= m * (m - 1) / 2

---

for(k=0; k < n;k++)
{
   for(l=0;l< n;l++)
   {

В этом случае внутренний цикл четко работает n * n times

---

Итак, число итераций точно равно

  (m * (m - 1) / 2) * (n * n)
= O(m^2 * n^2)

Очевидно, это предполагает, что if(condition) do something работает в постоянном времени.

Answer 3

Я предполагаю, что временная сложность "сделать что-то" равна O (S).

Давайте начнем с самого внутреннего цикла: его сложность по времени равна O (n * S), потому что он делает что-то n раз. Цикл, который охватывает самый внутренний цикл, имеет временную сложность O (n) O (n S) = O (n ^ 2 * S), потому что он выполняет внутренний цикл n раз.

Цикл, который оборачивает второй самый внутренний цикл, имеет временную сложность O (m-i) * O (n ^ 2 * S), потому что он выполняет операцию O (n ^ 2 * S) m-i раз.

Теперь самое сложное: для каждого i в диапазоне 0 ... m-1 мы выполняем операцию (m-i) * O (n ^ 2 * S). Сколько времени это занимает? (1 + 2 + 3 + ... + m) * O (n ^ 2 * S). Но (1 + 2 + ... + m) является суммой арифметической последовательности . Следовательно, сумма равна m * (m-1) / 2 = O (m ^ 2).

Вывод: Мы выполняем операцию O (n ^ 2 * S) примерно m ^ 2 раза. Временная сложность всего этого составляет O (m ^ 2 * n ^ 2 * S)

Answer 4

Для меня это выглядит как O (m ^ 2 n ^ 2), предполагая, что "что-то" является постоянным временем.

Хотя цикл j начинается с разных точек с каждым шагом, комбинированный эффект циклов i и j все еще равен m ^ 2.

Оценка самого неустановленного условия обычно была бы (по крайней мере) операцией с постоянным временем, поэтому, конечно, цикл не может быть быстрее, чем O (m ^ 2 n ^ 2) - если, конечно, «что-то» не включает разрыв , goto, исключение или что-либо еще, что выходит из одного или нескольких циклов раньше.

Все ставки отключены, если по какой-либо причине n или m не являются постоянными.

Answer 5

O (м² * n²) * сложность "чего-то"

Answer 6

O (m ^ 2 * n ^ 2 * (что-то сходится)).Если условие и что-либо выполняются в постоянное время, то O (m ^ 2 * n ^ 2).