Сложность Java двух рекурсивных методов

Question

public static String rec1 (String s) { 

    int n = s.length()/2; 
    return n==0 ? s : rec1(s.substring(n)) + rec1(s.substring(0,n)); 
} 


public static String rec2 (String s) { 
    return s.length()<=1 ? s : rec2(s.substring(1)) + s.charAt(0); 
} 

Почему сложность rec2 превышает rec1?

Я сделал 10.000 итераций на каждом и измеряли время выполнения с помощью System.nanoTime() со следующими результатами:

 
rec1: Stringlength: 200 Avgtime: 19912ns Recursive calls: 399 

rec1: Stringlength: 400 Avgtime: 42294 ns Recursive calls: 799 

rec1: Stringlength: 800 Avgtime: 77674 ns Recursive calls: 1599 

rec1: Stringlength: 1600 Avgtime: 146305 ns Recursive calls: 3199 

rec2: Stringlength: 200 Avgtime: 26386 ns Recursive calls: 200 

rec2: Stringlength: 400 Avgtime: 100677 ns Recursive calls: 400 

rec2: Stringlength: 800 Avgtime: 394448 ns Recursive calls: 800 

rec2: Stringlength: 1600 Avgtime: 1505853 ns Recursive calls: 1600 

Так на StringLength 1600 REC1 в 10 раз быстрее, чем rEC2. Я ищу краткое объяснение.

Answer 1

Согласно Time complexity of Java's substring(), String#substring Теперь копирует массив подложки, поэтому имеет O(n) временную сложность.

Используя этот факт, можно видеть, что rec1 имеет временную сложность O(n log n), тогда как у rec2 есть временная сложность O(n^2).

Начинать с начального String s = "12345678". Для простоты я взял длину, чтобы быть сила 2.

rec1:

1. s делится на "1234" и "5678".
2. Они разделены на "12", "34", "56", "78"
3. Они расщепляются на "1", "2", "3", "4", "5", "6", "7", "8"

Есть 3 шага здесь, потому что log(8) = 3. Каждый char копируется на каждом шаге, поэтому общее количество скопированных символов равно O(n log n). Когда String будет повторно собран в обратном порядке, выше Strings теперь соединены друг с другом с помощью конкатенации, используя следующие шаги:

1. Строки объединены в "21", "43", "65", "87"
2. Строки объединены в "4321", "8765"
3. Строки соединены, чтобы сделать "87654321".

Эта другая общая сумма O(n log n) копировавших персонажей!

rec2:

1. s делится на "1" и "2345678".
2. "2345678" Разделен на "2" и "345678".
3. "345678" Разделен на "3" и "45678".
4. "45678" Разделен на "4" и "5678".
5. "5678" раздел: "5" и "678".
6. "678" Разделен на "6" и "78".
7. "78" Разделен на "7" и "8".

В общей сложности 8 + 7 + 6 + 5 + 4 + 3 + 2 = 35 копировавших персонажей. Если вы знаете алгебру, это будет (n * (n+1))/2 - 1 скопированных персонажей в целом, поэтому O(n^2).

Если все это собрано в обратном порядке, количество символов копий будет равно O(n^2).

Answer 2

Давайте исследовать разницу в производительности:

String.substring() 

• подстрока действительно дешево в Java (не вплоть до Java 7 Update 6) потому что не копирует исходные данные, но только обновления коррекций на одном массиве ,

Строка перекрываться + оператор

• здесь возникает разница причина перекрываться + оператор использует StringBuilder в случае непредставления текстовых строк. Если вы развернете реализацию метода StringBuilder.append(), вы, наконец, найдете вызов System.arraycopy().

Таким образом, разница в том, что System.arraycopy() имеет дело с экспоненциально убывающей размер массива в то время как rec1 только с линейно уменьшением размера массива в rec2.

Answer 3

(Это исправленный вариант относительно сложности времени)

Хотя число рекурсий фактически линейно по п (так как рекурсия называется дважды на каждом уровне) есть разница между этими двумя способами, как так же как копирование персонажей.

Каждый из методов имеет внутреннее выполнение двух операций копирования - один для substring (в Java 7), и один для concat (в лице оператора +).

В rec2 он копирует правую часть строки снова и снова до тех пор, пока не останется только один символ. Таким образом, последний символ в строке скопирован глубина раз, а глубина - линейная. Таким образом, линейные шаги, умноженные на линейные копии (это фактически серия), дают O (n).

В rec1 каждый символ либо копируется в левую подстроку, либо в правую подстроку. Но символ не копируется более чем глубина раз - пока мы не дойдем до односимвольных подстрок. Поэтому каждый символ копируется log n раз. Хотя рекурсия вызывается дважды, она не вызывается на одни и те же символы, поэтому отмена журнала, вызванная двойным вызовом, не влияет на количество копий каждого символа.

То же самое относится к перестройке. Те же копии имеют место в обратном порядке.

Количество экземпляров - n символов, умноженное на глубина log n, дает O (n log n). Количество выполненных шагов - O (n), поэтому количество шагов менее значимо, чем количество копий, а общая сложность - O (n log n).

---

Кроме того, существует сложность пространства. rec1 переходит на глубину O (log n) в свою рекурсию, т. Е. Занимает пространство стека O (log n). Он делает это дважды, но это не меняет большой-O. Напротив, rec2 переходит на глубину O (n).

На моей машине, запуская два метода со строкой длиной 16384, результатом было переполнение стека для rec2. rec1 закончил без проблем. Конечно, это зависит от настроек JVM, но вы получаете изображение.