<p><code>mytri(n)</code>的时间复杂度是<code>O(1)</code>。<code>mydivs(n)</code>的时间复杂度是<code>O(n/2)</code>,也就是<code>O(n)</code>。<code>while (mydivs(mytri(n)) <= 500)</code>的时间复杂度是<code>O(n^3)</code>,因为它是循环中的循环,一个循环运行<em>N</em>次,另一个运行<em>N^2</em>次。。您可以将<code>mydivs(n)</code>的时间复杂度降低到<code>O(sqrt(n)</code>。你知道吗</p>
<pre><code>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.
</code></pre>
<h2><code>new_mydivs(n)</code>的时间复杂度是<code>O(sqrt(n))</code></h2>
<h2>找到一个250除数的数的代码执行时间</h2>
<pre><code>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)
</code></pre>
<p>输出:</p>
<pre><code>2162160.0
100.24735450744629
</code></pre>
<hr/>
<h2>250除数的代码执行时间:</h2>
<pre><code>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)
</code></pre>
<p>输出:</p>
<pre><code>2162160.0
0.22459840774536133
</code></pre>
<h2>对于500除数:</h2>
<pre><code>76576500.0
5.7917985916137695
</code></pre>
<h2>对于750除数:</h2>
<pre><code>236215980.0
17.126375198364258
</code></pre>
<p>性能大幅度提高。你知道吗</p>