我最近正在学习时间复杂度，我想知道计算 a^n 的算法的时间复杂度。我的答案是 O(n)。 然而，我正在考虑分而治之的方法。作为 a^n/2 * a^n/2 = a^n。是否有可能将算法 a^n 的时间复杂度变成 O(logn) 时间复杂度的算法，但我一直在思考这样的算法会是什么样以及它如何工作？
如果有人能与我分享他们的想法，我将不胜感激。
https://cp-algorithms.com/algebra/binary-exp.html 这篇文章讨论了同样的问题。