как написать рекуррентное отношение для заданного фрагмента кода

Question

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

Сначала я подумал, что цель этих отношений состоит в том, чтобы записать сложность алгоритма рекурсивного деления и покоя. Затем я столкнулся с вопросом в назначениях MIT, где попросили предоставить отношение повторения для итеративного алгоритма.

Как бы я на самом деле придумал рекуррентное отношение, учитывая некоторый код? Каковы необходимые шаги?

Действительно ли это правильно, что я могу записать любой случай, например, самый худший, лучший, средний случай с таким отношением?

Может ли кто-нибудь дать простой пример того, как фрагмент кода превращается в рекуррентное отношение?

Приветствия, Andrew

Answer 1

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

Например, рассмотрим функцию Фибоначчи ниже:

Fib(a) 
{ 
    if(a==1 || a==0) 
    return 1; 
    return Fib(a-1) + Fib(a-2); 
} 

Это три операции (сравнение, сопоставление, добавление), а также называет себя рекурсивно. Таким образом, отношение повторения составляет T(n) = 3 + T(n-1) + T(n-2). Чтобы решить эту проблему, вы должны использовать итеративный метод: начните расширять термины, пока не найдете шаблон. В этом примере вы можете развернуть T(n-1), чтобы получить T(n) = 6 + 2*T(n-2) + T(n-3). Затем разверните T(n-2), чтобы получить T(n) = 12 + 3*T(n-3) + 2*T(n-4). Еще раз, разверните T(n-3), чтобы получить T(n) = 21 + 5*T(n-4) + 3*T(n-5). Обратите внимание, что коэффициент первого Т-терма равен числам Фибоначчи, а постоянный член представляет собой сумму из них раз три: поиск, то есть 3*(Fib(n+2)-1). Что еще более важно, заметим, что последовательность возрастает экспоненциально; то есть сложность алгоритма O (2 ⁿ).

Тогда рассмотрим эту функцию для сортировки слиянием:

Merge(ary) 
{ 
    ary_start = Merge(ary[0:n/2]); 
    ary_end = Merge(ary[n/2:n]); 

    return MergeArrays(ary_start, ary_end); 
} 

Эта функция вызывает себя на половину ввода в два раза, а затем объединяет две половинки (с использованием O (N) работы). То есть, T(n) = T(n/2) + T(n/2) + O(n). Чтобы решить рекуррентные отношения этого типа, вы должны использовать Master Theorem. По этой теореме это расширяется до T(n) = O(n log n).

Наконец, рассмотрим эту функцию для вычисления Фибоначчи:

Fib2(n) 
{ 
    two = one = 1; 
    for(i from 2 to n) 
    { 
    temp = two + one; 
    one = two; 
    two = temp; 
    } 
    return two; 
} 

Эта функция вызывает себя не раз, и он перебирает O (N) раз. Следовательно, его рекуррентное соотношение равно T(n) = O(n). Это тот случай, о котором вы спрашивали. Это особый случай рекуррентных отношений без повторения; поэтому его очень легко решить.

Answer 2

Чтобы найти время работы алгоритма, мы должны сначала написать выражение для алгоритма, и это выражение сообщает время выполнения для каждого шага. Поэтому вам нужно пройти каждый шаг алгоритма, чтобы найти выражение. Например, предположим, что мы определили предикат isSorted, который примет в качестве входных данных массив a и размер n массива и вернет true тогда и только тогда, когда массив будет отсортирован в порядке возрастания.

bool isSorted(int *a, int n) { 
    if (n == 1) 
     return true;  // a 1-element array is always sorted 
    for (int i = 0; i < n-1; i++) { 
     if (a[i] > a[i+1]) // found two adjacent elements out of order 
     return false; 
    } 
    return true;   // everything's in sorted order 
} 

Очевидно, что размер ввода здесь будет просто равным n, размер массива. Сколько шагов будет выполнено в худшем случае, для ввода n?

Первое, если на счету заявление как 1 шаг

для цикла будет выполнять N-1 раз в худшем случае (при условии, внутренний тест не пинать нас), на общее время n-1 для теста цикла и приращения индекса.

Внутри цикла есть еще одна инструкция if, которая будет выполняться один раз на итерацию в течение всего n-1 раз, в худшем случае.

Последний возврат будет выполнен один раз.

Таким образом, в самом худшем случае, мы сделали 1+ (п-1) + (п-1) +1

вычисления, для общего времени выполнения Т (п) ≤1 + (n-1) + (n-1) + 1 = 2n, и поэтому мы имеем функцию синхронизации T (n) = O (n).

Так вкратце то, что мы сделали - >>

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

2. Итеративные утверждения, такие как циклы и внутреннее тело, будут принимать переменное время в зависимости от ввода. Имеет решение T (n) = O (n), как это происходит с нерекурсивной версией.

3.So ваша задача состоит в том, чтобы идти шаг за шагом и записать функцию в терминах п к calulate временной сложности

Для рекурсивных алгоритмов, вы делаете то же самое, только на этот раз, когда вы добавить время принятый каждым рекурсивным вызовом, выраженный как функция времени, которое требуется на его входе. Например, давайте перепишем, isSorted как рекурсивный алгоритм:

bool isSorted(int *a, int n) { 
    if (n == 1) 
     return true; 
    if (a[n-2] > a[n-1])   // are the last two elements out of order? 
     return false; 
    else 
     return isSorted(a, n-1); // is the initial part of the array sorted? 
} 

В этом случае мы по-прежнему ходить по алгоритму подсчета: 1 шаг для первого, если плюс 1 шаг для второй, если, плюс время isSorted будет принимать входной размер n-1, который будет T (n-1), дающий рекуррентное отношение

T (n) ≤1 + 1 + T (n-1) = T (n-1)) + O (1)

У какой есть решение T (n) = O (n), как это происходит с нерекурсивной версией.

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