一.時間復雜度
首先我們來看一個問題·：
題目：如果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("The possible a is {}, b is {}, c is {}".format(a,b,c)) end_time = time.time() print("time:{}".format(end_time-start_time)) print("finished")
這樣我們就可以得到結果：
The possible a is 0, b is 500, c is 500 The possible a is 200, b is 375, c is 425 The possible a is 375, b is 200, c is 425 The possible a is 500, b is 0, c is 500 time:190.9680194854736328 finished
我們可以通過這個程式來分析它的運算規模大小，假如說程式每執行一次，則計為1，那么一個回圈里則執行了1000次，三個回圈就執行了1000*1000*1000次，在最后一個變數C的回圈當中，還有if陳述句和print陳述句，這兩個都算是執行的步驟，因此我們將總體執行的步驟表示為：
T=1000^3*（1+1）
但是1000這個數字是可以更換的，可以變成2000,3000，可以隨著題目要求的變化而變化，這樣我們可以得到一個更為普遍的函式來表示這個時間復雜度（程式執行所需要的全部步驟就叫做時間復雜度，且我們一般將最壞時間復雜度稱為時間復雜度，最壞時間復雜度表示的是程式一旦完成這些步驟一定能夠完成所有的作業，因為有的時候程式完成一些步驟就會得到最后答案，但是我們不能夠使用最優時間復雜度，這太過特殊了），你可以將1000變為n，這樣就能得到以下函式的形式：
T(n)=n^3*2
二.大O表示法
之前我們已經發得到了上面這個程式的時間復雜度，現在我們來使用更為通識的大O表示法來表示它，這個表示法說白了就是忽略掉低次方的項，當然對于只有常數項的時間復雜度無法進行忽略，對于剛才我們得到的函式：T(n)=n^3*2，其中后面乘上的2相對平方而言來說是非常小的，因此可以忽略不計，用大O表示法可以表示為：
T(n)=O(n^3)
這樣就得到了我們這個程式時間復雜度的大O表示法的結果了，
下面是常見大O表示法的表示方法以及術語：
下面是練習：
第一個的答案是：O（1）
第二個的答案是：O（n）
第三個的答案是：O（n^2）
第四個的答案是：O（n^2）
今天有關時間復雜度和大O表示法的知識就到此結束了！希望你能夠有所識訓！
結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73558.html
標籤：其他