Сложность выполнения базовых рекурсивных функций - PullRequest
Новая
       13

Сложность выполнения базовых рекурсивных функций

0 голосов
/ 10 июня 2019

Я пытаюсь понять контраст между временем выполнения для этой функции 

public static String f(int N) {
    if (N == 0) return "";
    String s = f(N / 2);
    if (N % 2 == 0) return s + s;
    else            return s + s + "x";
}

и этой функции 

public static String f(int N) {
    if (N == 0) return "";
    if (N == 1) return "x";
    return f(N/2) + f(N - N/2);
}

, где конкатенация строк занимает время, пропорциональное размеруstrings.

Пока что я считаю, что первая функция вызывается log (N) раз для ввода N, а вторая 2log (N) раз.Это правильно?Кроме того, я не уверен, как думать о том, сколько операций происходит в каждом из этих вызовов.Я знаю, что для первой функции в базовом случае есть 0 операций (без конкатенации), затем 1 операция (конкатенация двух нулевых строк со строкой длины 1?), Затем 2 операции.Вообще я считаю, что строка, полученная при вызове с N, имеет длину N?Но я просто не знаю, с чего бы начать думать о том, как все это складывается.

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

1 Ответ

1 голос
/ 27 июня 2019

Для того, чтобы приблизиться к вашему анализу, я рекомендую упростить ваше повторение. У вас есть F (n / 2) + F (n-n / 2). Вторая половина этого может быть упрощена (F (n-n / 2) = F (2n / 2 - n / 2) = F (n / 2)). Это означает, что вы, по сути, вызываете f (n / 2) два раза для каждой итерации, что в действительности является 2log (n). У вас есть строго постоянные операции времени в обоих этих примерах (я думаю) за пределами повторения.

Насколько я могу судить, оба из них должны давать схожий вывод, за исключением того, что в первом примере вы будете использовать "x" для каждого нечетного n. Это должно привести к дополнительному n / 2 x, умноженному на log (n) количество x? Я не совсем уверен, правильно ли это. Я также считаю, что ваш первый пример выполняется за 2log (n), так как вы вызываете f (n / 2) дважды, пока n не станет 0.

Примечание: я не самый лучший в этом деле, но я сделал все возможное.

...