Анализ сложности времени

Question

Извините, у меня нет времени писать длинный контекстный сюжет. Это вопрос из практического экзамена, который я делаю в данный момент, и все мои ресурсы в университете находятся в автономном режиме (замечательный Uni, я знаю). Я полностью зациклен на том, как начать это. Может ли кто-нибудь пройти через меня? Я не самый лучший с математикой.

Рассмотрим следующий рекурсивный метод:

public static int triple(int x) { 
    if (x == 0) return 0; 
    else return add(3, triple(decrement(x))); 
} 

Если предположить, что в худшем случае производительность время для метода декремента является постоянным и что метод добавить линейна во втором параметре (т.е. время для дополнения (x, y) может быть выражен как by+a для некоторых констант b и a), получить наименьшее big O, что описывает наихудшие временные характеристики тройного метода в терминах x. Чтобы получить сложность для этого метода, определите и разверните отношения повторения для первых нескольких экземпляров метода (размеры проблем), а затем обобщите выражения , чтобы сформировать уравнение замкнутой формы для nth case. Покажите свои работы.

Answer 1

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

x | executions |    Executions 
------------------------------------- 
0 | T(0)      | 0 A(0) 
1 | T(1) + A(3,1) + T(0)  | 3 A(1) 
2 | T(2) + + A(3,1) + T(1) | 6 A(2) 
3 | T(3) + A(3,1)   | 9 A(3) 

    Time Complexity for T= T(n)+T(n-1)+...+T(n-n) 
    Number of add calls is linear O(n) 

    nth term for number of executions 
    Un = 3+(n-1)d 
     = 3+(n-1)3 

    the sum of the an arithmetic series making it O(n^2) 

Answer 2

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

Во-вторых, для каждого выполнения тройки, какая у вас наихудшая временная сложность? Подсказка: это определяется функцией add().

Тогда обобщайте.

Answer 3

Для конкретного x, triple будем называть рекурсивно с помощью 0, 1, 2, ... x. Назовем эти аргументы рекурсивными вызовами i. Когда аргумент равен i, второй аргумент add равен 3(i-1). Это означает, что стоимость такого вызова add линейна в i. Таким образом, каждый рекурсивный вызов является линейным в аргументе triple. Есть x таких вызовов, поэтому у вас есть сумма арифметических рядов (0 + 3 + 6 + ...) - и это O (n) сложность по времени.

Вы можете играть с этим кодом:

public class Test 
{ 
    static int time; 
    public static int triple(int x) { 
    if (x == 0) return 0; 
    else return add(3, triple(decrement(x))); 
    } 
    private static int add(int i, int j) { 
    System.out.println("Spending " + j); 
    time += j; 
    return i + j; 
    } 
    private static int decrement(int x) { time++; return x-1; } 
    public static void main(String[] args) { 
    for (int i = 1; i < 100; i+=10) { 
     time = 0; 
     System.out.format("triple(%d)=%d; time=%d\n", i, triple(i), time); 
    } 
    } 
} 

Answer 4

Хорошо, как я в конечном итоге его выводе (и спасибо за все хорошие люди размещения ответов, чтобы заставить меня идти) должен был принять совет Jochen и выработать быстрая карта сложности, которая сделала все намного проще.

Во-первых, обратите внимание, что вопрос предусматривает, что добавление - это время O (n).

Далее, основной иерархии вызовов "Трайпл":

n | Time complexity: 
------------------------------------------ 
1 | T(1) + (T(0) = 1 ) 
2 | T(2) + (T(1) = ...) 
3 | T(3) + (T(2) = ...) 

очевидно картина складывается ...

n | Time complexity 
------------------------------------------- 
n | T(n) + T(n - 1) 

Таким образом, оказывается, что Т (п) пора сложность n * T, где T временная сложность для тройного звонка. Учитывая, что источник роста для вызова от add и времени сложность add «s является O(n), временная сложность становится n * n или O(n^2)

Спасибо, ребята, дайте мне знать, если я использовал неправильную терминологию или что-то.

EDIT: часть добавления была выключена, но тем не менее.