为什么我的函数在输入值magnatude中使用Python时间限制？

Question

我正在尝试创建一个函数来测试python中的命令time。函数应该以m,n为参数，计算MODEXP(a,e,p)，其中p最多是2^m，第一种情况下e是2^n，第二种情况下是2^(n-1)，a是小于p的随机正整数

这是我的密码：

import random
def question_3(m,n):
    list = []
    for i in xrange(2,2**m):
        flag=True
        for num in list:
            if(i%num==0):
                flag=False
        if(flag):
            list.append(i)
            p = choice(list)
            a = randint(1,int(p)-1) 
            e = pow(2,n)
    return pow(a, e, p)

    time t = question_3(5,5) #non-Python syntax.

问题是这个函数不能在m和n大于20的情况下工作，我不知道为什么。你知道吗

Answer 1

你的代码在我的盒子上运行得很好。正如其他人所指出的，它是O（2**n），因此运行时间呈指数增长。这是我的时间安排：

m = n = 2; time needed:  1.90734863281e-05
m = n = 3; time needed:  1.50203704834e-05
m = n = 4; time needed:  2.21729278564e-05
m = n = 5; time needed:  4.38690185547e-05
m = n = 6; time needed:  9.41753387451e-05
m = n = 7; time needed:  0.000232934951782
m = n = 8; time needed:  0.000643014907837
m = n = 9; time needed:  0.00198698043823
m = n = 10; time needed:  0.00656795501709
m = n = 11; time needed:  0.0229339599609
m = n = 12; time needed:  0.082200050354
m = n = 13; time needed:  0.299206972122
m = n = 14; time needed:  1.09857010841
m = n = 15; time needed:  4.06366610527
m = n = 16; time needed:  15.0994331837
m = n = 17; time needed:  56.4191129208

对于m=n=100，大约需要1.3*10^49秒。你知道吗