计算2 ^ 5000的时间复杂度是多少？(What is the time complexity to calculate 2^5000?)

计算2 ^ 5000的时间复杂度是多少？(What is the time complexity to calculate 2^5000?)

计算2 ^ 5000的时间复杂度是多少？

我接近它，通过递归然后它导致O（N），其中N =数字的幂。 有没有办法减少这种时间复杂性？

What is the time complexity to calculate 2^5000 ?

I approached it, by recursion but then it leads to O(N) where N = power of a number. Is there any way to reduce this time complexity ?

最满意答案

我认为您对一般方法感兴趣，不仅仅是在这个给定的例子中。

您可以使用Log（N）运算通过平方逼近求幂来计算第N个整数幂

但请注意，数字2^N由大约N个二进制数字（位）组成，而在存储器中的简单写入是O（N）操作

I think that you are interested in general approach, not only in this given example.

You can calculate N-th integer power using Log(N) operations with exponentiation by squaring approach

But note that number 2^N consists of about N binary digits (bits) and simple writing in memory is O(N) operation