我在 NOI Linux 上测试了一下，对于 2 的 0 到 31 次方分别跑一遍 quick_power，记录结果和用时。

结论：不开 O2 的情况下，时间复杂度为 O(n)，开 O2 的情况下，时间复杂度为 O(log n)（因为用时很短，其实无法分辨究竟是 O(log n) 还是 O(1)）。

代码：

#include <iostream>
#include <iomanip>

double quick_power(double x, unsigned n) {
	if (n == 0)	return 1;
	if (n == 1)	return x;
	return quick_power(x, n / 2)
		 * quick_power(x, n / 2)
		 * ((n & 1) ? x : 1);
}

void test(unsigned n) {
	int beg_time = clock();
	quick_power(1.5, n);
	int end_time = clock();
	std::cout << "n: " << std::setw(10) << std::setfill(' ') << n << ", "
		  << "time: " << std::fixed << std::setprecision(6)
		  << (double)(end_time - beg_time) / CLOCKS_PER_SEC << '\n';
}

int main() {
	for (int i = 0; i < 32; i++)
		test((unsigned)1 << i);
	return 0;
}

测试结果（命令行）：

user@ubuntu:~/Desktop$ g++ csp-s1-15.cpp -o csp-s1-15
user@ubuntu:~/Desktop$ ./csp-s1-15
n:          1, time: 0.000003, result: 1.000000
n:          2, time: 0.000000, result: 1.000000
n:          4, time: 0.000000, result: 1.000000
n:          8, time: 0.000001, result: 1.000000
n:         16, time: 0.000001, result: 1.000000
n:         32, time: 0.000000, result: 1.000000
n:         64, time: 0.000001, result: 1.000001
n:        128, time: 0.000001, result: 1.000001
n:        256, time: 0.000002, result: 1.000003
n:        512, time: 0.000003, result: 1.000005
n:       1024, time: 0.000007, result: 1.000010
n:       2048, time: 0.000014, result: 1.000020
n:       4096, time: 0.000028, result: 1.000041
n:       8192, time: 0.000056, result: 1.000082
n:      16384, time: 0.000141, result: 1.000164
n:      32768, time: 0.000222, result: 1.000328
n:      65536, time: 0.000459, result: 1.000656
n:     131072, time: 0.000901, result: 1.001312
n:     262144, time: 0.001811, result: 1.002625
n:     524288, time: 0.003587, result: 1.005257
n:    1048576, time: 0.006661, result: 1.010541
n:    2097152, time: 0.010810, result: 1.021193
n:    4194304, time: 0.020025, result: 1.042835
n:    8388608, time: 0.039420, result: 1.087505
n:   16777216, time: 0.078831, result: 1.182667
n:   33554432, time: 0.157359, result: 1.398702
n:   67108864, time: 0.314778, result: 1.956366
n:  134217728, time: 0.629010, result: 3.827368
n:  268435456, time: 1.257726, result: 14.648743
n:  536870912, time: 2.514295, result: 214.585667
n: 1073741824, time: 5.044637, result: 46047.008328
n: 2147483648, time: 10.100698, result: 2120326975.987767
user@ubuntu:~/Desktop$ g++ csp-s1-15.cpp -o csp-s1-15 -O2
user@ubuntu:~/Desktop$ ./csp-s1-15
n:          1, time: 0.000001, result: 1.000000
n:          2, time: 0.000000, result: 1.000000
n:          4, time: 0.000000, result: 1.000000
n:          8, time: 0.000000, result: 1.000000
n:         16, time: 0.000000, result: 1.000000
n:         32, time: 0.000000, result: 1.000000
n:         64, time: 0.000001, result: 1.000001
n:        128, time: 0.000000, result: 1.000001
n:        256, time: 0.000000, result: 1.000003
n:        512, time: 0.000000, result: 1.000005
n:       1024, time: 0.000000, result: 1.000010
n:       2048, time: 0.000000, result: 1.000020
n:       4096, time: 0.000001, result: 1.000041
n:       8192, time: 0.000000, result: 1.000082
n:      16384, time: 0.000000, result: 1.000164
n:      32768, time: 0.000001, result: 1.000328
n:      65536, time: 0.000000, result: 1.000656
n:     131072, time: 0.000000, result: 1.001312
n:     262144, time: 0.000001, result: 1.002625
n:     524288, time: 0.000000, result: 1.005257
n:    1048576, time: 0.000000, result: 1.010541
n:    2097152, time: 0.000000, result: 1.021193
n:    4194304, time: 0.000000, result: 1.042835
n:    8388608, time: 0.000000, result: 1.087505
n:   16777216, time: 0.000000, result: 1.182667
n:   33554432, time: 0.000001, result: 1.398702
n:   67108864, time: 0.000000, result: 1.956366
n:  134217728, time: 0.000000, result: 3.827368
n:  268435456, time: 0.000001, result: 14.648743
n:  536870912, time: 0.000001, result: 214.585667
n: 1073741824, time: 0.000000, result: 46047.008328
n: 2147483648, time: 0.000000, result: 2120326975.987767
user@ubuntu:~/Desktop$