从简单的例子来看看算法的到底能改变什么?

「爱情、让人受尽委屈。」 2022-05-13 02:16 62阅读 0赞

>     先来看一道题:
>     
>     如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?

##  第一种写法: ##

import time
    
    start_time = time.time()
    
    for a in range(0, 1001):
        for b in range(0, 1001):
            for c in range(0, 1001):
                if a + b + c == 1000 and a ** 2 + b ** 2 == c ** 2:
                    print("a,b,c:",(a,b,c))
    
    end_time = time.time()
    print("一共耗时:%.2f"%(end_time-start_time))

## 第二种写法:只是少了一层循环而已 ##

import time
    
    start_time = time.time()
    
    # 这次只有2层循环
    for a in range(0,1001):
        for b in range(0,1001):
            c= 1000-a-b
            if a**2 +b**2 ==c**2:
                print("a,b,c:",(a,b,c))
    
    end_time = time.time()
    print("一共耗时:%.2f"%(end_time-start_time))

## 结果分析 ##

> 第一种的结果如下:
> 
>     a,b,c: (0, 500, 500)
>     a,b,c: (200, 375, 425)
>     a,b,c: (375, 200, 425)
>     a,b,c: (500, 0, 500)
>     一共耗时:111.88
>     
>     Process finished with exit code 0
> 
>     时间复杂度分析：
>     三层循环
>         T(n) = O(n*n*n) = O(n3)

>  第二种的结果如下:
> 
>     a,b,c: (0, 500, 500)
>     a,b,c: (200, 375, 425)
>     a,b,c: (375, 200, 425)
>     a,b,c: (500, 0, 500)
>     一共耗时:0.96
>     
>     Process finished with exit code 0
>     
>     时间复杂度：
>     
>     T(n) = O(n*n*(1+1)) = O(n*n) = O(n2)

从结果分析得知,

第一种三层循环--运行时间:111.88秒

第二种两层循环--运行时间:0.96秒

大大提高了运行效率!

**如果你和我有共同爱好,我们可以加个好友一起交流!**

**![1445380-20180903211901788-1752749014.png][]**

[1445380-20180903211901788-1752749014.png]: /images/20220513/7a642f1eb47949959f8f32f629b5d06a.png