Блог

насколько я понял, линейная сложность может быть представлена в виде простого цикла, а квадратичная сложность может быть представлена в виде вложенного цикла. Как можно представить кубическую и логарифмическую сложность?

Спасибо!

Простой цикл может иметь логарифмическую сложность, например

 for (i = 1; i <= N; i *= 2)
    ...
  

Как уже отвечали другие, тройной вложенный цикл будет иметь кубическую сложность.

Поскольку cubic равно O (n ^ 3), это будет три вложенных цикла.

Логарифмирование не так просто и обычно требует рекурсивного отношения. Например, сортировка слиянием равна O(n * log(n)), потому что она формирует дерево рекурсии высотой log (n), и для каждого уровня требуется операция объединения O (n).

• Кубический — три вложенных цикла
• Логарифмический — идея в том, что в каждом цикле цикла вы разбиваете набор входных данных на части (или каким-то образом уменьшаете его), а в следующем цикле обрабатываете сокращенный набор данных, поэтому в основном сложность существенно не возрастает при росте набора входных данных. Например, взгляните на алгоритм BinarySearch или любой другой алгоритм разделяй и властвуй.

Кубическая сложность — три вложенных цикла:

 foreach
   foreach
      foreach
      // actions
      end
   end
end
  

Пример сложности логарифма — двоичный поиск.

O (n ^ 3) может быть представлено тремя вложенными циклами.

O (log n) представлен циклом, в котором с каждой итерацией объем данных, которые необходимо обработать, уменьшается вдвое.