Преобразования из кода в рекуррентное соотношение

Question

Я учусь на экзамен, и я наткнулся на некоторых проблемы, мне нужно обратиться - решения базовых случаев:

Я конвертирование из Кодекса рекуррентного соотношения не в другой стороне вокруг

Пример 1:

if(n==1) return 0; 

Теперь рекуррентное соотношение к той части кода: Т (1) = 0

Как я понял? Посмотрев на n == 1, мы видим, что это сравнение со значением> 0, которое выполняет некоторую форму работы, поэтому мы устанавливаем «T (1)» и return 0; не делает любую работу так, мы говорим "= 0"

=> T(1) = 0; 

---

Пример 2:

if(n==0) return n+1*2; 

Анализ: п == 0 означает, что мы не делать какие-либо работы, таким образом Т (0), но возвращаем n + 1 * 2; делают работу таким образом «= 1»

=> T(0) = 1; 

---

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

Я не уверен, о них, которые я придумал сам по себе исчерпать возможности базовых случаев:

Example 3: if(n==m-2) return n-1; //answer: T(1) = 1; ? 
Example 4: if(n!=2) return n;  //answer: T(1) = 1; ? 
Example 5: if(n/2==0) return 1; //answer: T(1) = 1; ? 
Example 6: if(n<2) return;  //answer: T(1) = 0; ? 

Answer 1

Это трудно анализировать базовые случаи вне контекста кода, так что это может быть полезно, если вы разместили всю функцию. Однако, я думаю, ваша путаница возникает из предположения, что T (n) всегда представляет «работу». Я предполагаю, что вы занимаетесь классом по сложности, и вы узнали о рекуррентных отношениях как методе выражения сложности рекурсивной функции.

T (n) - это просто функция: вы подключаете число n (обычно положительное целое число), и вы получаете число T (n). Как и любая другая функция, T (n) ничего не значит сама по себе. Однако мы часто используем функцию с обозначением T (n), чтобы выразить время, требуемое алгоритмом для запуска на входе размера n. Это две отдельные концепции; (1) функцию T (n) и различные способы ее представления, такие как рекуррентное соотношение, и (2) количество операций, необходимых для запуска алгоритма.

Позвольте привести пример.

int factorial(n) 
{ 
    if (n > 0) 
     return n*factorial(n-1); 
    else 
     return 1; 
} 

Посмотрим, можем ли мы написать какую-либо функцию F (n), которая представляет вывод кода. хорошо, F (n) = n * F (n-1), с F (0) = 1. Почему? Ясно, что из кода результат F (0) равен 1. Для любого другого значения n результат F (n) = n * F (n-1). Это рекуррентное отношение является очень удобным способом выражения вывода рекурсивной функции. Конечно, я мог бы так же легко сказать, что F (n) = n! (факторный оператор), что тоже правильно. Это нерекурсивное выражение одной и той же функции. Обратите внимание, что я ничего не сказал о времени выполнения алгоритма или о том, как он работает. Я просто пишу математическое выражение для вывода кода.

Работа с временем работы функции немного сложнее, так как вам нужно решить, что вы имеете в виду под «работой» или «с операцией». Предположим, что мы не считаем «return» как операцию, но мы считаем умножение как операцию, и мы считаем условным (оператор if) как операцию. В этих предположениях мы можем попытаться написать рекуррентное соотношение для функции T (n), которая описывает, сколько работы выполняется, когда ввод n задан функции. (Позже я сделаю комментарий о том, почему это плохой вопрос.) Для n = 0 мы имеем условный (оператор if) и return, ничего другого. Итак, T (0) = 1. Для любого другого n> 0 мы имеем условное умножение, и для вычисления T (n-1) требуется множество операций. Таким образом, общее для п является:

T(n) = 1 (conditional) + 1 (multiply) + T(n-1) = 2 + T(n-1), 
T(0) = 1. 

Мы могли бы написать Т (п) в качестве рекуррентного соотношения: Т (п) = 2 + T (N-1), Т (0) = 1. Конечно, это также просто функция T (n) = 1 + 2n. Опять же, я хочу подчеркнуть, что это две разные функции. F (n) описывает выход функции, когда n является входом. T (n) описывает, как много работы выполняется, когда n является входом.

Теперь T (n), о котором я только что описал, является плохим с точки зрения теории сложности. Причина в том, что теория сложности - это не описание того, сколько работы требуется для вычисления функций, которые принимают только одно целое число в качестве аргумента. Другими словами, мы не рассматриваем работу, требуемую для функции вида F (n). Нам нужно что-то более общее: сколько требуется работы для выполнения алгоритма на входе размера n. Например, MergeSort является алгоритмом для сортировки списка объектов. Для выполнения MergeSort требуется nlog (n) операций, чтобы выполнить список n элементов. Обратите внимание, что MergeSort ничего не делает с номером n, скорее, он работает в списке размер n. Напротив, наша факториальная функция F (n) не работает на входе размера n: предположительно n является целым типом, поэтому, вероятно, это 32-битные или 64-битные или что-то, независимо от его значения. Или вы можете получить придирчивый и сказать, что его размер - это минимальное количество бит для его описания. В любом случае n - это вход, а не размер ввода.

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