模幂大O表示法

Question

我正在上一门算法设计和分析课程，我们重点关注常见算法的时间和空间复杂度，但我很难理解大 O 表示法/时间复杂度。对于这个项目，我们必须编写费马小定理来确定数字的素性，同时编写米勒-拉宾定理来捕获卡迈克尔数（例如 561）。我只是希望能对 Big O 表示法是什么以及为什么要使用我的模幂函数 (mod_exp) 进行简单的解释，因为它在两个函数中都使用了。这样我可以更好地理解它并尝试自己确定其他函数的时间和空间复杂度。

def mod_exp(x, y, N): 
    if y == 0:          # Time: Space: 
            return 1
    z = mod_exp(x, y//2, N)         # Time: Space: 
    if y % 2 == 0:
        return (z**2) % N   # Time: Space: 
    else:
        return (x*(z**2)) % N   # Time: Space: 
#Total Time: Total Space:

我唯一理解的是它递归地调用自身 N 次，但是 return 语句呢？由于它递归地返回 z^2 mod N 或 x * z^2 mod N 这些实例也是 O(n) 或者是指数实例，所以它将是 O(logn) 或 O(2^n)。

Answer 1

这很好地解释了大O。

你的

mod_exp

函数对我来说看起来像是 O(log y) 。所有回报的数学运算都是 O(1)。有些人可能会认为这不是真的，但在算法分析课上，算术运算复杂度为 O(1) 通常是一个合理的假设。

参数

x

和

N

具有误导性，因为它们在函数的递归调用之间不会改变，因此可以将它们视为全局变量或内联常量，实际上不会影响进行多少次递归调用。

对

mod_exp(x, y//2, N)

的调用是最有趣的部分。由于您在每次调用时将

y

除以 2，并且当

y == 0

（即

y == 0

是您的基本情况）时函数停止递归，因此您预计最多进行 O(log y) 次递归调用。

在计算机科学中，除非另有说明，

log

的底数被假定为

2

。 （在普通数学中，

log

的底数被假定为

10

。）

如果您不能立即理解为什么

y = y//2

只能在

y == 0

之前发生 O(log y) 次，请告诉我。这是一个知识差距，你应该积极努力弥补；这是算法分析的关键直觉。

您知道最多可以对

mod_exp

函数进行 O(log y) 次调用。并且您知道对该函数执行“单个”调用（不包括可能会或可能不会结果的“其他”递归调用）需要 O(1) 时间。 O(log y) 次调用 * 每次调用 O(1) 工作意味着您的最终答案是 O(log y)。