Строить рекуррентное отношение для этого кода?

Давайте посмотрим на код, чтобы увидеть, каким должно быть повторение.

Во-первых, давайте посмотрим на цикл:

    for i=1 to n
    {
       for j=i to 2i
       { 
           for k=j-i to j-i+100
               write (i, j, k);
       }
    }

Сколько работы это делает? Что ж, начнем с упрощения. Вместо того, чтобы j считать от i до 2i, давайте определим новую переменную j', которая считает от 0 до i. Это означает, что j' = j - i, и поэтому мы получаем это:

    for i=1 to n
    {
       for j' = 0 to i
       { 
           for k=j' to j'+100
               write (i, j' + i, k);
       }
    }

Ах, так намного лучше! Теперь давайте также перепишем k как k', где k' находится в диапазоне от 1 до 100:

    for i=1 to n
    {
       for j' = 0 to i
       { 
           for k'= 1 to 100
               write (i, j' + i, k' + j);
       }
    }

Отсюда легче увидеть, что этот цикл имеет временную сложность (n²), поскольку самый внутренний цикл работает O(1), а средний цикл будет выполняться 1 + 2 + 3 + 4 + ... + n = (n²) раз. Обратите внимание, что это не совсем 100n², потому что сумма не совсем n², но она близка.

Теперь давайте посмотрим на рекурсивную часть:

for i=1 to 7
    Alg(n-2);

Во-первых, это просто глупо! Нет причин, по которым вы когда-либо хотели бы сделать что-то подобное. Но при этом мы можем сказать, что это 7 вызовов алгоритма на входе размера n - 2.

Соответственно, мы получаем это рекуррентное соотношение:

T(n) = 7T(n - 2) + (n²) [если n 3]

T(n) = (1) [иначе]

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

• Есть 1 вызов размера n.
• Есть 7 вызовов размера n - 2.
• Есть 49 вызовов размера n - 4.
• Есть 343 вызова размера n - 6.
• ...
• Есть 7^k вызовов размера n - 2k

Отсюда мы немедленно получаем нижнюю границу (7^n/2), так как это количество вызовов, которые будут сделаны. Каждый вызов работает O(n²), поэтому мы можем получить верхнюю границу O(n²7^n/2). Истинная ценность лежит где-то там, хотя я, честно говоря, не знаю, как понять, что это такое. Извини за это!

Надеюсь это поможет!

Формальный метод заключается в следующем:

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

Алгоритм с двумя рекурсивными вызовами имеет сложность 2^n; с 3 рекурсивными вызовами сложность 3^n и так далее.