blocks|key|1447584|text|我认为这种算法的复杂性与a无关。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1447585|在回顾复杂性时，我认为循环数是由于m而导致的最高复杂度的主要指标。|1447586|在b的值中运行，如果b>0时，我们可以看到如下数字：|1447587|​|1447588|📷|atomic|offset|length|1447589|1447590|有趣的是，我们看到每个2的倍数(即1,2,4,8,16,32,64)的n个循环的增加。|1447591|粗略地说，我认为这个算法的复杂性与O(log2(n))密切相关。|1447592|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/8bbf618a9a7a1bda00dbef6bfe64ec1b.png|imageAlt^0|0|0|0|0|0|1|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|13|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|14|8|@]|9|@$K|15|L|16|1|17]]|A|$]]|$1|M|3|G|5|6|7|18|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|19|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1A|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|S|$T|$5|U|V|W|A|$X|Y|Z|-4]]]]

I think the complexity of this algorithm is independent of a.

When reviewing the complexity, I think the number of loops is your main index for the highest complexity due to m. 

Running through values of b, we can see following number if b > 0 computations as: 

<a href="https://i.stack.imgur.com/FuN1I.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FuN1I.png" alt="Plot of number of n(b&gt;0) computations for a give b value"></a>

Interestingly, we see an increase in n loops for each multiple of 2 (i.e. 1,2,4,8,16,32,64). 

Roughly speaking, I would say the complexity of this algorithm closely follows O(log2(n)).

blocks|key|1319948|text|另外，我知道，乘以2位x位和y位会导致x*y%2B(x%2By)异常操作。|type|blockquote|depth|inlineStyleRanges|entityRanges|data|1319949|这(一般)不是真的。一个处理器将在一个确定的循环数中将两个数字相乘，无论它们是否大。除非你是处理巨大的数字，你应该考虑，关于渐近复杂性(O)，乘法作为一个运算，同样适用于加法，除法，.|unstyled|1319950|在您的代码中，每个循环迭代有三个操作(if+b+%25+2+==+1，可能是result+=+result*a，a+=+a*a，b+=+b+//+2)。复杂性仅取决于循环的迭代次数，即:+log2(b)，因为b在每次迭代中被除以两次。|offset|length|style|CODE|1319951|对于庞大的数字，您有两个操作可能会对渐近复杂性产生影响：result+=+result*a和a+=+a*a。Cpython使用Karatsuba增殖，如果n是数字的数字数，则为O(n%5Elog2+2(3))。|1319952|我只想详细介绍一下a*a。当你取一个数字的平方，你大概把数字的数目乘以二。考虑log2(b)循环：a*a在第一次迭代中取O(n%5Elog2+2(3))，在第二次迭代中取O(2n%5Elog2+2(3))，在第二迭代中取O(4N%5Elog2+2(3))，在最后一次迭代中取O(Bn)%5Elog2+2(3)。之和是O(b*log2+2(B)*n)%5Elog2+2(3)，如果我没有错的话！|1319953|对于a*a，如果您被绑定到O(x*y)乘法算法，那么对于您的log2(b)循环，|1319954|第一次迭代的O(n%5E2)；|unordered-list-item|1319955|第二次迭代的O(2n)%5E2；|1319956|第三次迭代O((4n)%5E2)；|1319957|K次迭代的O(2%5E(k-1)*n)%5E2.|1319958|这是O(b%5E2+*+n%5E2)+=+O(2%5E2m+*+n%5E2)，我认为(现在没有时间检查！)。|1319959|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/python/cpython/blob/master/Objects/longobject.c#L3269^0|0|0|J|D|10|H|1I|7|1Q|A|0|S|H|1A|7|1R|B|0|0|9|3|1D|3|0|2|3|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|19|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1A|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|1B|8|@$G|1C|H|1D|I|J]|$G|1E|H|1F|I|J]|$G|1G|H|1H|I|J]|$G|1I|H|1J|I|J]]|9|@]|A|$]]|$1|K|3|L|5|D|7|1K|8|@$G|1L|H|1M|I|J]|$G|1N|H|1O|I|J]]|9|@$G|1P|H|1Q|1|1R]]|A|$]]|$1|M|3|N|5|D|7|1S|8|@$G|1T|H|1U|I|J]|$G|1V|H|1W|I|J]]|9|@]|A|$]]|$1|O|3|P|5|D|7|1X|8|@$G|1Y|H|1Z|I|J]]|9|@]|A|$]]|$1|Q|3|R|5|S|7|20|8|@]|9|@]|A|$]]|$1|T|3|U|5|S|7|21|8|@]|9|@]|A|$]]|$1|V|3|W|5|S|7|22|8|@]|9|@]|A|$]]|$1|X|3|Y|5|S|7|23|8|@]|9|@]|A|$]]|$1|Z|3|10|5|D|7|24|8|@]|9|@]|A|$]]|$1|11|3|-4|5|D|7|25|8|@]|9|@]|A|$]]]|12|$13|$5|14|15|16|A|$17|18]]]]

<blockquote>
 Also, I know that multiplying 2 number of x bits and y bits will
 result in x*y+(x+y) arithemtic operations.
</blockquote>

That's not (in general) true. A processor will multiply two numbers in a defined number of cycles whether they are big or not. Unless you are dealing with huge numbers, you should consider, regarding asymptotic complexity (O), the the multiplication as one operation, and the same applies for addition, division, ...

In your code, you have three of four operations per iteration of the loop (<code>if b % 2 == 1</code>, maybe <code>result = result*a</code>, <code>a = a*a</code>, <code>b = b // 2</code>). The complexity depends only on the number of iterations of the loop, that is: log2(b), because b is divided by two in each iteration.

For huge numbers, you have two operations that might have an impact on asymptotic complexity: <code>result = result*a</code> and <code>a = a*a</code>. Cpython uses the <a href="https://github.com/python/cpython/blob/master/Objects/longobject.c#L3269" rel="nofollow noreferrer">Karatsuba multiplication</a>, which is O(n^log2(3)) if n is the number of digits if the numbers.

I will just elaborate on <code>a*a</code>. When you take the square of a number, you roughly multiply the number of digits by two. Consider the log2(b) loops: <code>a*a</code> take O(n^log2(3)) in the first iteration, O(2n^log2(3)) int the second, O(4n^log2(3)) int the second, ..., O(bn)^log2(3)) in the last. The sum is O((b*log2(b)*n)^log2(3)), if I'm not wrong!

For <code>a*a</code>, , if you are bound to a O(x*y) mutlplication algorithm, then you have, for your log2(b) loops,

<ul>
<li>O(n^2) for the first iteration;</li>
<li>O((2n)^2) for the second iteration;</li>
<li>O((4n)^2) for the third iteration;</li>
<li>O((2^(k-1)*n)^2) for the k th iteration.</li>
</ul>

That's O(b^2 * n^2) = O(2^2m * n^2) I think (don't have the time to check now!).

blocks|key|1447632|text|嗯，经过一些分析，我认为power方法的迭代次数将在2%5E(2i-1)*n%2B(2%5E(i-1)%2B2%5Ei*n%2B(2%5Ei*n)%5E2%2B2%5E(i%2B1)*n的i(从0到m-1)上求和，并且得到复杂度：O(4%5Em*n%5E2)是非常直接的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1447633|entityMap^0|C|5|Q|19|2L|A|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|O|8|@]|D|@]|E|$]]]|G|$]]

Well, after some analyzing, I think that the number of iterations of the <code>power</code> method will be sum on i (from 0 to m-1) of: <code>2^(2i-1)*n+(2^(i-1)+2^i*n+(2^i*n)^2+2^(i+1)*n</code> and the it's pretty straight forward to get the complexity: <code>O(4^m*n^2)</code>

I have the following implementation of iterated squaring:

<pre><code>def power(a, b):
 result = 1
 while b &gt; 0:
 if b % 2 == 1:
 result = mult(result, a)
 a = mult(a, a)
 b = b // 2
 return result
</code></pre>

The <code>mult()</code> method multiplies 2 given numbers, when if one is of length of <code>x</code> bits and the other one is of length of <code>y</code> bits, the number of operations the multiplication will take is <code>x*y+(x+y)</code> operations, which I need to consider in the complexity analysis.

And I'm trying to find an <code>O()</code> notation bound of the number of arithemtic operations done as a function of <code>n</code> and <code>m</code> when a is n-bits long, and b is m-bits long. I need to take into consideration only the multiplication lines, and check for the worst case.

The worst case is when <code>b</code> is an m-bit number where all <code>m</code> binary digits are 1, and then I have <code>m</code> iterations of the loop where in each iteration the if condition is true.

What I dont know how to do is how I should consider in my computation the fact that <code>a</code> grows for each iteration? How to I put it in some sort of finite sum with probably geometric progression that I can compute?

Thanks

Iterated Squaring Time Complexity

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有以下迭代平方的实现：def power(a, b):  result = 1  while b > 0:    if b % 2 == 1:      result = mult(result, a)    a = mult(a, a)    b = b // 2  return resultmult()方法乘以2...

问迭代平方时间复杂度
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问迭代平方时间复杂度EN