利用字典提高算法效率

Question

第n个三角形数被定义为1+2+…+n之和。我正在研究一个项目Euler问题，该问题要求找到具有超过500个除数的最小三角形数，因此（在Python中）我编写了两个函数mytri(n)和mydiv(n)，分别计算第n个三角形数和n的除数。然后，我使用了while循环，循环直到mydiv(mytri(n))大于或等于500：

import math

def mytri(n):
    return n*(n+1)/2

def mydivs(n):
    num = 0
    max = math.floor(n/2)
    for k in range(1,max+1):
        if n%k == 0: 
            num += 1
    return num+1

n = 1
while (mydivs(mytri(n)) <= 500): n += 1

print(mytri(n))

我以为我写mytri()和mydiv()的效率很高，但是根据一些测试，这个程序似乎很快就变得很笨拙了。计算第一个超过100个除数的数字不到一秒钟，但是计算第一个超过150个除数的数字大约需要8-9秒，这表明它在时间上可能是指数的？我在计算复杂性或编写高效算法方面没有太多经验，但我曾经看到过一个使用字典的例子（我想是记忆化？）为了极大地改进计算斐波那契数的递归算法，我想知道这里是否可以使用类似的思想。你知道吗

例如，第n个三角形数可以表示为n（n+1）/2，因此在不丧失一般性的情况下，它是奇数和偶数的乘积，例如n和（n+1）/2。如果您可以将每个数字的除数存储在字典中（最多n个），那么您就不必在mydiv()中重新进行计算，而只需引用字典即可。唯一的问题是找出n和（n+1）/2之间的哪些除数重叠以获得正确的除数。这是合理的攻击线吗？还是我在这里遗漏了什么？你知道吗

另外，我的算法的时间复杂度是多少？我将如何计算它？你知道吗

Answer 1

关于：时间复杂性。有两个循环，一个循环在另一个循环中，一个循环到N，另一个循环到N^2。这就给出了O（N^3）时间复杂度。你知道吗

您可以使用字典来保存部分结果，但是总体复杂度仍然是O（N^3），但是常数因子较小，因为您仍然需要循环处理其余的值。你知道吗

Answer 2

mytri(n)的时间复杂度是O(1)。mydivs(n)的时间复杂度是O(n/2)，也就是O(n)。while (mydivs(mytri(n)) <= 500)的时间复杂度是O(n^3)，因为它是循环中的循环，一个循环运行N次，另一个运行N^2次。。您可以将mydivs(n)的时间复杂度降低到O(sqrt(n)。你知道吗

def new_mydivs(n):
    res=set()
    for i in range(1,int(n**0.5)+1):
        #print(i)
        if n%i==0:
            res.update([i,n//i])
        #print(res)
    return len(res)    #returns the number of divisors.

new_mydivs(n)的时间复杂度是O(sqrt(n))

找到一个250除数的数的代码执行时间

import time
import timeit
import math
def mytri(n):
    return n*(n+1)/2
def mydivs(n):
    num = 0
    max = math.floor(n/2)
    for k in range(1,max+1):
        if n%k == 0: 
            num += 1
    return num+1

def main():
    n = 1
    while (mydivs(mytri(n)) <= 250): n += 1

    print(mytri(n))

startTime=time.time()
main()
print(time.time()-startTime)

输出：

2162160.0
100.24735450744629

---

250除数的代码执行时间：

import time
import timeit
import math
def mytri(n):
    return n*(n+1)/2
def mydivs(n):
    res=set()
    for i in range(1,int(n**0.5)+1):
        #print(i)
        if n%i==0:
            res.update([i,n//i])
        #print(res)
    return len(res)    #returns the number of divisors.

def main():
    n = 1
    while (mydivs(mytri(n)) <= 250): n += 1

    print(mytri(n))

startTime=time.time()
main()
print(time.time()-startTime)

输出：

2162160.0
0.22459840774536133

对于500除数：

76576500.0
5.7917985916137695

对于750除数：

236215980.0
17.126375198364258

性能大幅度提高。你知道吗