Блог

Несмотря на то, что я прочитал некоторые предыдущие вопросы здесь, в stackoverflow, и посмотрел несколько видеороликов, включая этот, сложность времени и пространства идет прямо над моей головой. Мне нужно найти временную и пространственную сложность этого алгоритма

 public static int aPowB(int a, int b){
        if(b == 0){
            return 1;
        }
        int halfResult = aPowB(a, b/2);
        if(b%2 == 0){
            return halfResult * halfResu<
        }
        return a * halfResult * halfResu<
    }
  

Объяснение ответа было бы оценено, чтобы я мог попытаться понять. Спасибо.

Прежде всего, входными данными являются a и b , поэтому мы можем ожидать, что сложность времени / пространства будет зависеть от этих двух параметров.

При использовании рекурсивных алгоритмов всегда старайтесь сначала записать рекуррентное соотношение для временной сложности T . Здесь это

 T(a, 0) = O(1)              // base case
T(a, b) = T(a, b/2)   O(1)  // recursive call   some O(1) stuff at the end
  

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

 T(a, b) = O(log b)
  

(Если вы не знаете решение с трудом, просто спросите себя, сколько раз вы можете разделить b на 2, пока не нажмете 0.)

Сложность пространства также O(log b) связана с глубиной стека рекурсии.