Рекуррентное отношение алгоритма
void doSomething(int *a, int left, int right){
if (left == right){
for (int j = 0; i < right; ++j)
cout << a[j];
cout << endl;
return;
}
for (int i = left; i < right; ++i){
std::swap(a[left], a[i]);
doSomething(a, left + 1, right);
std::swap(a[left], a[i]);
}
}
«Выведите рекуррентное отношение для приведенного выше алгоритма. Предположим, что базовый случай равен T (1) = right. Также предположим, что функция swap обменивает значения своих двух аргументов за время O (1) и для рекуррентного отношения T ( n), пусть n = вправо-влево + 1. «
Нас попросили найти отношение повторения кода, приведенного выше. Мы смогли сделать вывод, что первый оператор if просто печатает содержимое массива всякий раз, когда left == right. Нижняя часть — рекурсивное утверждение, но мы не знаем, как проанализировать его сложность. Любая помощь будет оценена!
Решение
swap не имеет значения. Это влияет на то, что напечатано, но не влияет на время выполнения алгоритма. Итак, давайте посмотрим, что происходит:
Вызов doSomething(arr, j, j) печать j вещи.
Вызов doSomething(arr, i, j) марки j-i звонки в doSomething(arr, i+1, j),
Давайте немного переопределим переменные и определим f(i) как doSomething(arr, j-i, j), Сюда f(0) это базовый случай. И теперь правило повторения можно переписать так:
Вызов f(i) марки i звонки в f(i-1),
Что делает рекуррентное соотношение довольно ясным:
T(n) = n * T(n-1)
T(1) = O(n)
что сказать:
T(n) = O(n! * n)
Излишне говорить, что это довольно большое время выполнения!
Другие решения