시간복잡도
a^n는 직관적으로 해석하면 a를 n번 곱한다는 뜻이다. (당연)
그러면 시간복잡도 또한 단순하게 O(n) 일 것이다. (당연2)
거듭제곱을 빠르게 구하는 알고리즘은 총 2가지가 있는데,
이 두가지 알고리즘 모두 O(log n) 만에 거듭제곱을 구할 수 있다.
Fast Exponential Algorithm
많이들 사용하고, 쉽게 구현이 가능한 알고리즘이다.
구현법부터 적어놓은 후, 나중에 시간되면 추가로 설명까지 적을 예정입니다.
top-down
def fast_power(a, n):
if n < 1:
return 1
if n == 1:
return x
tmp = fast_power(a, n // 2)
if n % 2 == 1:
return a * tmp * tmp
else:
return tmp * tmpexample
ex) a = 7, b = 15
| n | 15 | 7 | 3 | 1 |
|---|---|---|---|---|
| tmp | 7^7 | 7^3 | 7 | |
| ret | 7 × 7^7 × 7^7 | 7 × 7^3 × 7^3 | 7 × 7 × 7 | 7 |
bottom-up
def fast_exponential(a, n):
ret = 1
while n > 0:
if n & 1 == 1:
ret = (a * ret)
a *= a
n = n >> 1
return retexample
ex) a = 7, b = 15
| n | 15 | 7 | 3 | 1 |
|---|---|---|---|---|
| LSB | 1 | 1 | 1 | 1 |
| ret | 7^1 | 7^2×7 | 7^4×7^3 | 7^8×7^7 |
| a | 7^2 | 7^4 | 7^8 | 7^16 |
Square and Multiply
이번에 스터디를 통해서 처음 알게된 거듭제곱 알고리즘이다.
위의 fast-expoenetial 알고리즘과 매우 흡사한 형태로 진행된다.
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
using lld = long long;
int main() {
int a, b, mod;
cin >> a >> b >> mod;
bitset<10> bs(b);
string b_binary = bs.to_string();
b_binary = b_binary.substr(b_binary.find('1'));
lld c = 0, f = 1;
for (auto binary : b_binary) {
c *= 2;
f = (f * f) % mod;
if (binary == '1') {
c++;
f = (f * a) % mod;
}
}
cout << f << "\n";
return 0;
}example
ex) a = 7, b = 560, mod = 561
