Big O: Что лучше?

Question

Я новичок в записи Big-O, поэтому мне нужен небольшой совет.Скажем, у меня есть выбор из двух алгоритмов: один с несколькими циклами for подряд или один с тремя вложенными циклами for.Например, один структурирован подобным этому:

    for(int i = 0; i < a.length; i++)
    {
       // do stuff
    }

    for(int i = 0; i < b.length; i++)
    {
       for(int j = 0; j < c.length; j++)
       {
          // do something with b and c
       }
    }

    for(int i = 0; i < d.length; i++)
    {
       // do stuff
    }

А другой структурирован следующим образом:

for(int i = 0; i < a.length; i++)
{
   for(int j = 0; j < b.length; j++)
   {
      for(int k = 0; k < c.length; k++)
      {
         // do stuff
      }
   }
 }

Эти примеры могут показаться не практичными, но я думаю,пытаясь проиллюстрировать мои реальные вопросы: какова большая нотация O для каждого метода и будет ли алгоритм с 3 вложенными циклами всегда менее эффективным, чем алгоритм с множеством дважды вложенных циклов (но не 3)?

Answer 1

что такое большая буква O для каждого метода

Большой O цикла с n шагами, вложенными в цикл с m шагами, равен O(n * m). Большой O цикла с n шагами, за которым следует один с m шагами: O(n + m) = O(max(n,m)).

Итак, ваш первый метод - O( max(a.length, b.length * c.length, d.length)), а второй - O( a.length * b.length * c.length). Какой из них лучше, зависит от того, d.length больше или меньше a.length * b.length * c.length.

и будет ли алгоритм с тремя вложенными циклами всегда менее эффективным, чем алгоритм с множеством дважды вложенных циклов (но не 3)?

Это зависит от того, сколько шагов каждая петля имеет по отношению к другой. Если все циклы имеют одинаковое количество шагов, 3 вложенных цикла всегда будут хуже, чем 2 вложенных.

Answer 2

Не обязательно. Используя a , b и c для представления ваших переменных, ваш первый пример - O (a + b * c + d), а второй - O ( а * б * в). Вероятно, последнее хуже, но это очень сильно зависит от переменных здесь - d может быть самой важной переменной в первом примере, и это будет довольно трудно сравнивать со вторым - если мы не предполагаем, что второе не ' * имеет коэффициент d (скажем, какой-то оптимизации)

Кроме того - три цикла не обязательно означают менее эффективную, хотя это часто имеет место. Операторы if во внешних циклах могут привести к тому, что внутренние циклы не будут выполняться, что может означать O (n ² ), несмотря на наличие трех вложенных циклов. Иногда построение алгоритма может показаться чем-то одним, но после более тщательного анализа мы обнаруживаем, что, хотя он выглядит как O (n ³ ), он фактически подчиняется O (n ² ).

Answer 3

В биг-о у вас есть правило:

O(a + b) = O(max(a, b))

Поэтому, если вы запускаете несколько циклов друг за другом, сложность алгоритма определяется наиболее сложным циклом.

Ваш второй пример имеет O (a * b * c). Это будет сложнее, чем в первом примере, если d

[с a, b, .. Я имею в виду a.length, b.length, ... соответственно]