Нижняя граница времени работы этого Алгоритм Построения для худшего случая

Question

У меня есть алгоритм следующим образом:

и даже у меня есть anwser для нахождения нижней границы этого алгоритма:

Но проблема в том, что я не могу этого понять: когда мы устанавливаем i> = n/2, но n/4 < = j < = n/2, то в этом алгоритме j не может получить какое-либо значение, которое, как вы видите в в ответ говорится, что средняя петля итерации n/4?

Я действительно смущен почему.

Answer 1

ОК, я не уверен, в какой части вас смущают, но позвольте мне перефразировать нижестоящее пояснение из вашего реферата, и, возможно, часть замешательства прояснится.

Прежде всего, подход нижней границы (вид очевидных вещей, но опущенный в вашем абстрактном виде и может быть неочевидным для начинающих студентов). Если вы представляете множество всех возможных значений (i, j, k), мы не хотим считать их всех, но будем считать только меньшие подмножества из них, определенные определенными произвольными ограничениями. Оказывается, проще вычислить нижнюю границу подмножества, чем на всем множестве (потому что вы можете делать простую математику, такую ​​как умножение нижних границ диапазонов из-за этих ограничений), и транзитивно это также будет нижней границей для всего набора ,

Теперь эти произвольные ограничения выбираются следующим образом: 1) Посмотрите только на i значения> = n/2. Это означает, что вместо того, чтобы смотреть на [1..n], мы смотрим на [n/2..n]. 2) Принимая во внимание предыдущее ограничение, также ограничьте j: посмотрите на значения j в диапазоне [n/4..n/2]. Слово «рассмотреть» в вашем тексте относится как к (1), так и (2)). Обратите внимание, что причина, по которой мы можем это сделать, состоит в том, что [n/4..n/2] всегда является подмножеством диапазона [1..i], поскольку мы уже решили, что мы рассматриваем только случаи, когда i> = n/2 , Поэтому ограничение [1..i] на [n/4..n/2] правильное дело, чтобы получить некоторую нижнюю границу.

Теперь, когда мы знаем, что i является [n/2..n] (по крайней мере, n/2), а j является [n/4..n/2] (по крайней мере, n/4), существует n/2 * n/4 комбинаций возможных (i, j) пар. Для каждой из этих пар внутренний цикл будет выполнять по крайней мере n/4-1 итераций (я не уверен, почему -1, возможно, означает округление?), Поэтому получаем n/2 * n/4 * (n/4-1) кортежи (i, j, k) - омега (n^3).

Если небольшим подмножеством вариантов является омега (n^3), то исходный набор также является омегой (n^3).

P.S. Я не понял, почему вы сказали «n/4 < = j < = n/2, тогда в этом алгоритме j не может получить никакого значения». n/4 меньше n/2, поэтому при достаточно больших n значениях j диапазон будет иметь некоторые числа.

Answer 2

Вы можете визуализировать число итераций в цикле, как

for(i in [1..n]) 
    for(j in [1..i]) 
    statement; 

как (при п = 6):

x 
x x 
x x x 
x x x x 
x x x x x 
x x x x x x 

это даст вам сложность O(N*N). Число итераций во внутреннем контуре (в вашем примере) также зависит от N, поэтому оно даст вам еще один множитель N (третье измерение). Таким образом, x es заполнит 1/32 (?) Объема куба. Но поскольку это образование кубов, сложность будет равна O (N³)

Answer 3

Мне кажется, что количество итераций в среднем цикле должно всегда быть меньше или равно числу итераций во внутреннем цикле, потому что k всегда будет перейдите от 1 до j.

Ниже приведен пример того, где я прошел через петлю.

array[1,2,3,4,5] 

will produce the following iterations with the restrictions on the loops: 

i=3,j=2,k=1 //i starts at 3 because of n/2 minimum 
      //j can't go below or above 2 because of condition on middle loop 
i=3,j=2,k=2 
i=4,j=2,k=1 
i=4,j=2,k=2 
i=5,j=2,k=1 
i=5,j=2,k=2 

3 iterations of outer loop (at least n/2) 
1 iteration of middle loop for each outer loop iteration (NOT at least n/4) 
2 iterations of inner loop for each iteration of middle loop (at least n/4 - 1) 

Текст, возможно, только что заменил описания для нижних двух петель. Если это так, ответ будет правильным.

Независимо от того, важно отметить, что он работает в O (n^3) времени.