Нижняя граница времени выполнения этого псевдокода

Question

for i = 0 to n do 
for j = n to 0 do 
for k = 1 to j-i do 
print (k) 

Мне интересно, о нижнем пределе выполнения вышеуказанного кода. В примечаниях я читаю это объясняет, нижняя граница выполнения быть

с объяснением;

Чтобы найти нижнюю границу времени работы, рассмотрит значение I, такие, что 0 = < < я = п/4 и значение у, такие, что 3n/4 = < < J = п. Заметим, что для каждой из n^2/16 различных комбинаций i и j самый внутренний цикл выполняется как минимум n/2 раза.

Может кто-нибудь объяснить, откуда пришли эти номера? Они кажутся мне произвольными.

Answer 1

Есть n итерации первого цикла и для каждого из них n итерации второй петли. В общей сложности это n^2 итерации второго цикла.

Теперь, если вы рассматриваете только нижнюю четверть возможных значений для i, то у вас есть n^2/4 итерации внутреннего цикла слева. Если вы также учитываете только верхнюю четверть значений для j, то у вас есть n^2/16 итерации внутреннего цикла слева.

Для каждой итерации этих ограниченных случаях вы имеете j-i >= 3n/4-n/4 = n/2 и поэтому самый внутренний цикл повторяется по крайней мере n/2 раз для каждого из этих n^2/16 итераций внешних петель. Поэтому полное число итераций самого внутреннего цикла составляет не менее n^2/16*n/2.

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

Значения не являются произвольными, поскольку вы можете использовать многие другие. Но это некоторые простые, которые делают возможным аргумент j-i >= 3n/4-n/4 = n/2. Например, если вы взяли только нижнюю половину итераций i и верхнюю половину итераций j, тогда у вас будет j-i >= n/2-n/2 = 0, что приведет к Omega(0), что не представляет интерес. Если бы вы взяли что-то вроде нижней десятой и верхней десятой, это все равно работало бы, но цифры были бы не такими приятными.

Answer 2

Я не могу объяснить диапазоны из вашей книги, но если вы попытаетесь продолжить использование нижеуказанной методологии, я надеюсь, что станет более понятным найти то, что вы ищете.

Идеальный способ для внешнего контура (индекс я) и внутреннего цикла (индекс J) заключается в следующем, так как j - i >= 1 должен быть устойчивым, так что самый внутренний цикл будет выполняться (по крайней мере, один раз в каждом дело).

Выполненное разложение было выполнено, поскольку диапазон j from i to 0 игнорируется самой внутренней петлей.заказ

for (i = 0 ; i < n ; i ++) { 
    for (j = n; j > i ; j --) { 
     for (k = 1; k <= j - i ; k ++) { 
      printf(k); 
     } 
    } 
} 

Этот алгоритм сложности роста T(n) является:

Таким образом, ваш алгоритм делает итерации более чем алгоритм выше (j goes from n to 0).

Использование Sigma нотации, вы можете сделать это:

Где c представляют стоимость выполнения print(k) и c' является стоимость выполнения происходящих итераций, которые не связаны с сокровенным петля.