Простой алгоритм сложности

Question

У меня есть алгоритм, и мне нужна помощь в поиске сложность его (сжатые возможно верхняя граница)

for(int i = 0; i < n/2; i++) 
    for(int j = 0; j < n/4; j++) 
     for(int k = 0; k < n; k++) 
      x++; 

Мой анализ является то, что если п не будут разделены на каждый цикл, было бы O(n^3). Эта сложность по-прежнему сохраняется, поскольку каждый цикл «for» сокращает каждую операцию до сложности O(log n), поскольку она делит n каждый раз, когда цикл выполняется, делая его меньше и меньше (меньше, чем O(n)).

Я бы сказал, что ответ находится между O(log n) и O(n^3). Не могли бы вы помочь мне получить максимально возможную связь?

Answer 1

начать с внутреннего цикла:

for(int k = 0; k < n; k++) 
    x++; 

, очевидно, О (п).

теперь один слой выше, что:

for(int j = 0; j < n/4; j++) 

представляет собой О (п), поскольку она занимает п/4 для J, чтобы достигнуть п и мы знаем, что О (п/4) = О (n)

и, как это для внешнего цикла, это O (n). Сложность O(n^3), потому что у вас есть три вложенных цикла, каждый из которых имеет O (n), а не их влияние на друг друга.

Answer 2

for(int i = 0; i < n/2; i++) --> n/2 
    for(int j = 0; j < n/4; j++) --> n/4 
     for(int k = 0; k < n; k++) --> n 
      x++; 

Следовательно, общая сложность O((n^3)/8) что O(n^3)

Answer 3

Предположим, что для каждого шага требуется время C. Для k-loop, время взято C n. Для j-цикла время, затраченное на завершение итерации (C n) n/4 = C (n^2)/4 Для i-цикла время, затраченное на завершение итерации, равно (C * (n^2))/4) п/2 = С (п^3)/8

Так Общее время, затраченное = (С/8) * (п^3)

в С/8 является константой, что могут быть проигнорированы при рассмотрении Big-O Notation. Таким образом, Сложность времени = O (n^3).