算法的复杂性（威尔逊检验）

Question

请问威尔逊函数在 O(..) 方面的复杂度是多少：

#fonction calculant le factorielle de n (n!) :

def factorielle(n):
    p=1
    for i in range(2,n+1):
        p=p*i
    return p

#fonction testant la primalité de p en utilisant le théorème de wilson :

def wilson(p):
    if factorielle(p-1)%p==p-1:
        return True
    return False

Answer 1

计算wilson函数的复杂度很简单，复杂度基于处理器中的"instruction"运行s，所以基本上只有循环，影响复杂度，wilson 的 if 和 factorielle 复杂度的复杂度为 1，因此 O(1 + O(factorielle)).

所以，为了计算 factorielle 复杂度，我们分析了循环，你可以看到那个循环，运行s n-1 次，对吧？所以 factorielle 复杂度是 O(n-1)，这使得 factorielle 复杂度是 O(n)，因为它只取决于 n 到代码将运行

算法的复杂性（威尔逊检验）

Complexity of an Algorithm (wilson test)

python

complexity-theory