求幂运算即计算X^N，如果使用N-1次乘法自乘，其复杂度为O（N）。最近在看《数据结构与算法分析》时，有一种用递归快速求幂的算法，程序如下：
long int Pow(long int X, unsigned int N) { if (N == 0) return 1; if (N == 1) return X; if (N % 2 == 0) return Pow(X*X, N / 2); else return Pow(X*X, N / 2)*X; }该算法的复杂度为O（logN）。 下面给出一种不用递归，复杂度仍为O（logN）的计算方法：
#include <stdio.h> int main(void) { int X, N, ans, i; int *x; while (scanf_s("%d %d", &X, &N) != EOF) { printf("%d^%d = ", X, N); x = (int *)malloc(sizeof(int) * (N + 1)); i = 0; ans = 1; x[0] = X; while (N > 0) { x[i + 1] = x[i] * x[i]; if (N % 2 == 1) ans *= x[i]; i++; N /= 2; } printf("%d\n", ans); } }