логарифмическая сложность представлена ​​с помощью цикла?

Question

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

foreach
   foreach
      foreach
      // actions
      end
   end
end

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

Answer 4

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

Answer 5

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

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