티스토리 뷰

공부

[Recursive] numberPower?

승가비 2018. 9. 6. 23:38
728x90

[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;
}


728x90

'공부' 카테고리의 다른 글

[DataStructure] Stack?  (0) 2018.09.07
[DataStructure] bracketComplete? - Stack, Map, String  (0) 2018.09.07
[Recursive] isTwoPower?  (0) 2018.09.06
[DB] 트랜잭션(작성중)  (0) 2018.08.27
[OS] Process & Thread  (0) 2018.08.20
댓글