как найти рекуррентное соотношение из алгоритма

Я пытаюсь понять рекуррентные отношения. Я нашел способ определить максимальный элемент в массиве целых чисел с помощью рекурсии. Ниже приведена функция. При первом вызове n — это размер массива.

int ArrayMax(int array[], int n) {
    if(n == 1)
        return array[0];
    int result = ArrayMax(array, n-1);
    if(array[n-1] > result)
        return array[n-1];
    else
        return result;
}

Теперь я хочу понять рекуррентное отношение и как оттуда перейти к нотации big-O. Я знаю, что T(n) = aT(n/b) + f(n), но не понимаю, как получить, какими должны быть a и b.


c++ recursion recurrence big-o
person AdamK    schedule 21.07.2017    source источник
comment
Нотация большого O будет рассчитываться по количеству операций в наихудшем сценарии. Кажется, ваша функция начинается в конце массива и работает в обратном направлении, сравнивая все значения в массиве. Итак, на первый взгляд, ваша функция равна O(n). Вот хорошее объяснение.   -  person avery_laird    schedule 21.07.2017

Ответы (2)


arrow_upward
3
arrow_downward

a — это «количество рекурсивных вызовов», а b — это «на сколько частей вы разбиваете данные», что интуитивно понятно. Обратите внимание, что параметр внутри рекурсивного вызова не обязательно должен быть n разделен на что-то, в общем случае это любая функция n, которая описывает, как изменилась величина ваших данных.

Например, бинарный поиск выполняет один рекурсивный вызов на каждом уровне, разбивает данные на 2 и выполняет постоянную работу на каждом уровне, поэтому он имеет T(n) = T(n/2) + c. Сортировка слиянием каждый раз разбивает данные на две части (расщепление требует работы, пропорциональной n) и рекурсивно работает с обоими подмассивами, поэтому вы получаете T(n) = 2T(n/2) + cn.

В вашем примере у вас будет T(n) = T(n-1) + c, поскольку вы делаете один рекурсивный вызов и «разделяете данные», каждый раз уменьшая их размер на 1.

Чтобы получить из этого нотацию большого O, вы просто делаете замены или расширяете. На вашем примере это легко:

T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c = ... = T(0) + nc

Если принять T(0) = c0, некоторую «базовую константу», то получится T(n) = nc + c0, что означает, что проделанная работа находится в O(n).

Пример с бинарным поиском аналогичен, но вы должны сделать замену — попробуйте разрешить n = 2^m и посмотрите, что вы можете с этим сделать. Наконец, вывод большого обозначения O, например. T(n) = T(sqrt(n)) + c действительно классное упражнение.

Изменить. Существуют и другие способы решения рекуррентных отношений. Стандартным методом является Основная теорема. Но доказательство не очень хорошее, и описанный выше метод работает для каждого повторения, к которому я когда-либо применял его. И... ну, это просто веселее, чем подставлять значения в формулу.

person hnefatl    schedule 21.07.2017

arrow_upward
0
arrow_downward

В вашем случае рекуррентное отношение:

T(n) = T(n-1) + constant

И основная теорема говорит:

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

Здесь основная теорема не может быть применена, потому что для основной теоремы b должно быть больше, чем 1 (b>1) А в вашем случае b=1

person Ghulam Moinul Quadir    schedule 21.07.2017