티스토리 뷰

알고리즘

[Recursive] numberPower?

seunggabi 승가비 2018. 9. 6. 23:38

[Recursive] numberPower?


n의 x 승을 구하는 가장 빠른 방법.


// n^x 구하기
// Time: O(logN) - N/2 줄여나가면서 갯수 반씩 감소하므로
// Space: O(logN) - 스택 깊이

#include <iostream>
using namespace std;

int numberPower(int n, int x) {
// n^0 == 1
if(x == 0) return 1;
// n^1 == n
if(x == 1) return n;
// n^3 == n * n^2
if(x % 2 == 1) return n * numberPower(n*n, x/2);
// n^4 == n^2 * n^2
return numberPower(n*n, x/2);
}

int main() {
int n, x;

cin >> n >> x;
cout << numberPower(n, x) << endl;
return 0;
}


댓글
댓글쓰기 폼