在O(n)时间内运行的指数乘法算法? [英] exponential multiplication algorithm that runs in O(n) time?

问题描述

我正在阅读算法教科书，但对此问题感到困惑:

I am reading an algorithms textbook and I am stumped by this question:

假设我们要计算值x ^ y，其中x和y为正 分别具有m位和n位的整数.解决问题的一种方法是对y-1乘以x.您能给出一种仅使用O(n)个乘法步骤的更有效的算法吗?

Suppose we want to compute the value x^y, where x and y are positive integers with m and n bits, respectively. One way to solve the problem is to perform y - 1 multiplications by x. Can you give a more efficient algorithm that uses only O(n) multiplication steps?

这将是一个分而治之的算法吗? y-1与x的乘积将在theta(n)中运行，对不对? ..我不知道从哪里开始这个问题

Would this be a divide and conquer algorithm? y-1 multiplications by x would run in theta(n) right? .. I don't know where to start with this question

推荐答案

为分而治之应用简单的递归. 在这里，我发布了一个更像伪代码的文件.

Apply a simple recursion for divide and conquer. Here i am posting a more like a pseudo code.

x^y :=
    base case: if y==1 return x;
        if y%2==0:  
            then (x^2)^(y/2;
        else 
            x.(x^2)^((y-1)/2);

这篇关于在O(n)时间内运行的指数乘法算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！