時間複雜性和實驗結果

Question

我有兩個算法A和B，在邏輯圖上工作，我想比較它們在時間上的效率。

當我計算時間複雜度爲兩種算法，我發現：

Time Complexity of A: O(2*n*n) 
Time Complexity of B: O((n*n)/2) 

根據維基百科，http://en.wikipedia.org/wiki/Time_complexity 我們忽略係數當我們計算的時間複雜度，這將產生：

Time Complexity of A: O(n^2) 
Time Complexity of B: O(n^2) 

我做的第二步是通過實驗來計算每種算法對不同大小的圖形所需的時間。在下面，x軸表示圖中節點的數量，y軸是以秒爲單位的時間。

正如你所看到的，有兩種算法對大圖的差異大。我的問題是：這是否合理？是否有可能有兩種算法具有相同的時間複雜度，但在實踐中存在時間上的巨大差異？謝謝。

Answer 1

是的，這是絕對合理的。計算複雜性並不能表明算法的精確程度 - 它反映了它如何對輸入大小的變化做出反應。

這不是一個巧合漸近複雜度被稱爲漸近而不是「相同」。