See an article on the lot, (https://github.com/pezy/LeetCode/blob/master/082.%20Pow (x % 20 n)/README. Md) there is a question
(int x, int pow unsigned n) {
if (! N) return 1;
Else if (n& 0 x1) return x * pow pow (x, n/2) * (x, n/2);
Else, return pow pow (x, n/2) * (x, n/2);
}
Why the time complexity of the algorithm above: O (n), space complexity: O (1).

CodePudding user response:

I summarize the way to teach you, how many times can as cycle time complexity, space complexity is the procedure to apply for a room to store variable
The problem is, like you need a space to store pow (x, n/2) variables, so the space complexity of O (1); Recursive loop n times, so the time complexity is O (n)