数据结构基础(((x^2+1))^2+1)^2......时间复杂度为什么是2logN

Question

书上原文:求幂运算, 要计算X^N, 如果N为偶数, 那么X^N = X^(N/2) * X^(N/2) , 如果N为奇数, 那么X^N = X^(N/2) * X^(N/2) * X.例如: X^62次,算法将如下进行, 它只用到了9次乘法X^3=(X^2)X, X^7=(X^3)^2X, X^15=(X^7)^2X, X^31=(X^15)^2X, X^62=(X^31)^2显然, 所需要的乘法次数最多是2logN.图片:通过这个例子和一个前辈的指明, 我总结出X^N = ((((x^2)^2+1)^2+1)^2+1)...., 但是如果通过这个求出时间复杂度为2logN?