16. 数值的整数次方

文档摘要

数值的整数次方题目链接牛客网题目描述给定一个 double 类型的浮点数 x和 int 类型的整数 n，求 x 的 n 次方。解题思路 --> 最直观的解法是将 x 重复乘 n 次，x\x\x...\x，那么时间复杂度为 O(N)。因为乘法是可交换的，所以可以将上述操作拆开成两半 (x\x..\x)\ (x\x..\x)，两半的计算是一样的，因此只需要计算一次。而且对于新拆开的计算，又可以继续拆开。这就是分治思想，将原问题的规模拆成多个规模较小的子问题，最后子问题的解合并起来。本题中子问题是 x n/2 ，在将子问题合并时将子问题的解乘于自身相乘即可。但如果 n 不为偶数，那么拆成两半还会剩下一个 x，在将子问题合并时还需要需要多乘于一个 x。