確定算法的運行時間以比較兩個陣列

Question

我想知道如何確定以僞代碼編寫的算法的運行時間，以便我可以熟悉運行時間。舉例來說，你如何知道一個算法的運行時間，它將比較兩個數組以確定它們是否不相同？

數組1 = [1,5,3,2,10,12]數組2 = [3,2,1,5,10,12] 因此，這兩個數組並不相同，因爲它們排序不同。

我的僞代碼是：

1）
2）設置的第二指針設置當前指針到第一數目在第一陣列第一數目在第二陣列
3），而（當前指針=「「）比較！與
移動當前指針到下一個號碼在其它陣列
4相同的位置元件）如果（當前指針==第二指針） 第二指針移動到下一個數

5）否則（輸出數組是不一樣） end loop

所以我假設第一次我的代碼是正確的。我知道第4步只執行一次，因爲它只需要1次匹配來顯示數組就不一樣了。所以第4步只需要一定的時間（1）。我知道第1步和第2步也只執行一次。

到目爲爲我知道運行時間是3 +？ （？是循環本身的運行時間）

現在我迷失了循環部分。循環是否運行n次（n是數組中的數字？），因爲最壞的情況可能是每一個數字都匹配？我是否以正確的方式考慮運行時間？

如果有人可以幫忙，我會感激。

謝謝！

Answer 1

你是對的。運行時間是O（n），其中n是陣列中元素的數量。每次向陣列中添加1個元素時，在最壞的情況下，您必須再次執行循環1次。

Answer 2

你在問什麼叫做時間複雜度你的算法。我們討論使用所謂的Big-O表示法的算法的時間複雜度。

Big-O符號是一種方法，用於說明我們的算法在輸入該尺寸的最差情況下，相對於算法輸入的大小，採用的大致步驟數。

您的算法運行在O(n)時間（發音爲「big-oh of n」或「order n」或有時我們只是說「線性時間」）。

您已經知道步驟1,2和4都以相對於數組大小的恆定步數運行。我們說這些步驟運行在O(1)時間（「恆定時間」）。

因此，讓我們考慮第3步：

如果有n個數組中的元素，則步驟3需要做ñ比較在最壞的情況下。所以我們說第3步需要O(n)時間。

由於該算法在步驟3上花費了O(n)時間，並且所有其他步驟都更快，所以我們說您的算法的總時間複雜度爲O(n)。

當我們編寫O(f)時，其中f是一些函數，我們的意思是該算法對於較大的值在某個常數因子f內運行。

以你的算法爲例。對於n的較大值（比如n = 1000），該算法不需要精確的n個步驟。假設一個比較需要5個指令來完成你的算法，在你選擇的機器上。 （它可以是任何常數，例如我只選擇5）。並且假設步驟1,2,4都採取了一些不變的步驟，這三個步驟共計10條指令。

然後對於n = 1000的算法將採取：

步驟1 + 2 + 4 = 10個指令。步驟3 = 5 * 1000 = 5000條指令。

這是一個總的5010個指令。這是大約5 * n條指令，這是一個常數因子n，這就是爲什麼我們說它是O(n)。

對於非常大的n，f = 5*n + 10中的10變得越來越微不足道了，因爲這樣做的原因是，我們只需簡單地將函數f is in O(n)減少到f is within a constant factor of n for large n即可。

通過這種方式可以很容易描述的想法，像f1 = n^2 + 2二次函數總是比喜歡f2 = 10000*n + 50000任何線性函數較大，當n足夠大，可以通過寫F1爲O(n)和f2爲O(n^2)。