Какова временная сложность этого конкретного метода?

Question

class Tower { 
     public void moveDisks(int n, Tower Destination, Tower Buffer) { 
     if (n > 0) { 
      moveDisks(n-1, Buffer, Destination); 
      moveTopto(Destination); 
      Buffer.moveDisks(n-1, Destination, this); 
     } 
    } 
} 

Вот код к методу, о котором я говорил выше. Это часть алгоритма, который решает классическую проблему Hanoi Tower. Я просто не могу окутать голову во временную сложность для этого, так как он имеет довольно рекурсию.

Это метод в классе Tower. moveTopto - O(1), поэтому не должно влиять на время выполнения.

Answer 1

Это зависит от временной сложности moveTopto и buffer.moveTopto.

В основном, чтобы вычислить сложность, вам придется добавить время. Время на n будет Время n-1, а также время для moveTopto плюс время для buffer.moveTopto plus an constant. Теперь вы увидите, что он будет иметь как минимум O(N), но может иметь более высокий уровень, особенно если buffer.moveTopto имеют непостоянную временную сложность.

Если вы имеете в виду Buffer.moveTopto, тогда время будет примерно в два раза больше времени для n-1, то есть вы бы получили t(n) = 2*t(n-1)+constant. Это дает O(2^n).

Answer 2

Хорошее объяснение рекурсивного анализа алгоритмов сложности Video Tutorial

PS. Если вы слишком ленивы, чтобы открыть ссылку и понять и просто хотите получить ответ - сложность ~ O (2^n)