在Java中檢查splay樹操作的複雜性

Question

我已經在Java中實現了splay樹（插入，搜索，刪除操作）。現在我想檢查算法的複雜度是否爲O（logn）。有沒有什麼辦法通過改變輸入值（節點數）和檢查運行時間來檢查這個問題？比如說，通過輸入1000,100000等輸入值並檢查運行時間還是有其他方法？

Answer 1

嚴格來說，通過運行n的某些值，您無法找到該算法的時間複雜度。我們假設你已經運行它的值爲n_1, n_2, ..., n_k。如果該算法對任何n <= max(n_1, ..., n_k)進行的操作都是n^2，對於任何較大的值爲n的操作都會執行10^100操作，但它具有恆定的時間複雜度，即使它看起來像您所擁有的點的二次方程。

但是，您可以通過運行某些值來評估在輸入大小爲n（因爲後者具有嚴格的形式定義，我甚至不稱其爲時間複雜度，因爲後者有嚴格的形式定義）的輸入需要完成的操作次數的n和看比率T(n1)/T(n2)和n1/n2。但即使在「真實」算法的情況下（意思是它不是第一段中描述的病態），您應該注意輸入的「結構」（例如，一種快速排序算法，第一個元素作爲樞軸在O(n log n)平均運行一個隨機輸入，所以如果生成不同大小的隨機數組，它將看起來像一個O(n log n)，但它運行在O(n^2)時間爲一個反向排序數組）。總結一下，如果你需要弄清楚它是否足夠快，從實際的角度來看，你有一個想法如何典型的輸入到你的算法看起來像，你可以嘗試生成不同大小的輸入，並看到執行時間如何增長。

但是，如果您需要數學意義上的運行時綁定，則需要在數學上證明算法的某些屬性和邊界。

在你的情況下，我會說隨機輸入測試可能是一個合理的想法（因爲有一個數學證明，一個操作的時間複雜度是一個splay樹的O(log n)），所以你只需要檢查你實施的樹確實是一個正確的展示樹。一個註釋：我建議嘗試不同的查詢模式（如按照排序/反向順序插入元素等），因爲即使不平衡樹也可以非常快地工作，只要輸入是「隨機」的即可。