- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
平时我比较懒,按如下方式计算模逆:
def inv(a,m):
return 1 if a==1 else ((a-inv(m%a,a))*m+1)//a
print(inv(100**7000,99**7001))
但我很想知道传递更多信息的方法,即 Bezout 定理的解决方案(而不是一对定理中的一个),在实践中是否会产生更快或更慢的算法:
def bez(a,b):
# returns [x,y,d] where a*x+b*y = d = gcd(a,b) since (b%a)*y+a*(x+(b//a)*y)=d
if a==0: return [0,1,b] if b>0 else [0,-1,-b]
r=bez(b%a,a)
return [r[1]-(b//a)*r[0],r[0],r[2]]
def inv(a,m):
r=bez(a,m)
if r[2]!=1: return None
return r[0] if r[0]>=0 else r[0]+abs(m)
print(inv(100**7000,99**7001))
我惊奇地发现后者比前者跑得快50多倍!但是两者都使用几乎相同数量的递归调用和每次调用 1 个整数除法和 1 个模运算,并且操作数的位长平均大约是前者的两倍(因为涉及的参数相同),所以我只期望它的时间复杂度大约是后者的 4 倍,而不是后者的 50 倍。
So why am I observing this strange speedup?
请注意,我使用的是 Python 3,我在运行 online 时观察到这一点,在顶部添加以下代码以停止 Python 解释器提示超出最大递归深度或堆栈空间:
import resource,sys
sys.setrecursionlimit(1000000)
resource.setrlimit(resource.RLIMIT_STACK,[0x10000000,resource.RLIM_INFINITY])
最佳答案
我终于明白了。假设初始输入是 n 位整数。在典型情况下,除了对 inv
或 inv2
的第一次调用外,递归调用的参数大小平均仅相差 O(1),并且有 O(n ) 平均递归调用,都是由于一些数论现象。这种 O(1) 大小差异意味着这两种方法实际上具有截然不同的平均时间复杂度。我的问题中隐含的假设是两个 n 位整数的乘法或除法大约需要 O(n^2) 时间;这适用于最坏的情况(对于教科书乘法),但不适用于快速方法的平均情况!
对于快速方法,可以证明当p,q > 0时,bez(p,q)
返回的三元组[x,y,d]满足abs(x) ≤ q 和 abs(y) ≤ p。因此,当每次调用 bez(a,b)
执行 b%a
和 (b//a)*r[0]
时,模由于平均 size(b)-size(a) ∈ O(1) 且 abs(r[0]) ≤ a,除法和乘法每个都需要 O(size(a)) 时间。因此,总时间大约为 O(n^2)。
然而,对于慢速方法,当每次调用inv(a,m)
时执行((a-inv(m%a,a))*m+1)//a
,我们有一个与 a 大小大致相同的 a-inv(m%a,a),所以这个除法是两个整数,其中第一个大约是第二个大小的两倍,这需要 O(大小(a)^2) 时间!因此,总时间大约为 O(n^3)。
的确,模拟结果与上述分析非常吻合。作为引用,使用快速方法 inv(100**n,99**(n+1))
where n = 1400·k for k∈[1..6] take time/ms 17,57,107,182,281,366
,同时使用慢速方法,其中 n = 500·k for k∈[1..6] 花费时间/ms 22,141,426,981,1827,3101
。它们分别与 9·k^2+9·k 和 13·k^3+8·k^2 非常吻合,平均分数误差分别为 ≈3.3% 和 ≈1.6%。 (我们包括前两个最高阶项,因为它们的贡献很小但很重要。)
关于algorithm - 模块化逆的奇怪 Python 加速,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42457205/
我有这种来自 Google map 自动完成的奇怪行为(或者我可能错过了某事)...想法?奇怪的: 您在输入中输入某物,例如“伦敦” 您按 [ENTER] 你按下 [CLEAR] 按钮 你点击进入'输
这段代码与《Learning Java》(Oracle Press Books)一书中的代码完全一样,但它不起作用。我不明白为什么它不起作用,它应该起作用。我用 OpenJDK 和 Sun JDK 7
示例 1 中究竟发生了什么?这是如何解析的? # doesnt split on , [String]::Join(",",("aaaaa,aaaaa,aaaaa,aaaaa,aaaaa,aa
我需要获得方程式系统的解决方案。为此,我使用函数sgesv_()。 一切都很好,它使我感到解决方案的正确结果。 但是我得到一个奇怪的警告。 警告:从不兼容的指针类型传递'sgesv_'的参数3 我正在
我目前在制作动画时遇到一个奇怪的问题: [UIView animateWithDuration:3 delay:0
alert('works'); $(window).load(function () { alert('does not work'); });
我的代码: public class MyTest { public class StringSorter implements Comparator { public
我正在学习 JavaScript。尝试理解代码, function foo (){ var a = b = {name: 'Hai'}; document.write(a.name +''
这个问题不太可能帮助任何 future 的访问者;它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关,这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用,visit
这按预期工作: [dgorur@ted ~]$ env -i env [dgorur@ted ~]$ 这样做: [dgorur@ted ~]$ env -i which date which: no
struct BLA { int size_; int size()const{ return size_; } } int x; BLA b[ 2 ]; BLA * p = &b[
我有以下代码: #test img {vertical-align: middle;} div#test { border: 1px solid green; height: 150px; li
我想大多数使用过 C/C++ 的人都对预处理器的工作原理有一定的直觉(或多或少)。直到今天我也是这么认为的,但事实证明我的直觉是错误的。故事是这样的: 今天我尝试了一些东西,但我无法解释结果。首先考虑
我想为 TnSettings 做 mock,是的,如果通过以下方法编写代码,它就可以工作,问题是我们需要为每个案例编写 mock 代码,如果我们只 mock 一次然后执行多个案例,那么第二个将报告异常
我的项目中有以下两个结构 typedef volatile struct { unsigned char rx_buf[MAX_UART_BUF]; //Input buffer over U
Regex rx = new Regex(@"[+-]"); string[] substrings = rx.Split(expression); expression = "-9a3dcb
我的两个应用程序遇到了一个奇怪的问题。这是设置: 两个 tomcat/java 应用程序,在同一个网络中运行,连接到相同的 MS-SQL-Server。一个应用程序,恰好按顺序位于 DMZ 中可从互联
我目前正在与 Android Api Lvl 8 上的 OnLongClickListener 作斗争。 拿这段代码: this.webView.setOnLongClickListener(new
这个问题不太可能帮助任何 future 的访问者;它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况相关,这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用,visit
只是遇到了奇怪的事情。我有以下代码: -(void)ImageDownloadCompleat { [self performSelectorOnMainThread:@selector(up
我是一名优秀的程序员,十分优秀!