有沒有辦法讓StoogeSort更加曲線？

我目前正在學習算法分析和它們各自的運行時間，並且我遇到了一個名爲Stooge sort的排序算法，它的行爲真奇怪的方式真的引起了我的注意。我試圖使用由我的教授創建的程序來確定運行時間，但是我擁有的點數非常少，因爲運行時開始以非常快的速度增長，並且我無法讓我的計算機執行一整天的計劃。有沒有辦法讓StoogeSort更加曲線？

我的問題是：有沒有辦法使算法的行爲更像曲線而不改變其複雜性？因爲我到目前爲止計算出了5個有用的點（這些點是Stooge排序「梯形圖」圖改變後的第一個實數，重新考慮了排序數組的大小），但這並不像我需要的那麼多。

我使用的是Stooge Sort的維基百科頁面上提供的算法。

來源

2015-09-20 SrKurtz

「更像曲線」是什麼意思？它_does_表現得像一條曲線。它很快就會變得陡峭。這是時間複雜性的結果。 –

是的，我知道，但我想知道是否有什麼我可以改變，而不會搞亂複雜性，使圖中「步驟」之間的點不會突然改變，改變連續的速度，如曲線。對不起，我不擅長解釋問題。 – SrKurtz

你試過了什麼樣的陣列尺寸？ –

五點數據太少，不能說它不像曲線。

事實上，你可以找到一個相當準確的曲線擬合數據：

來源：http://mycurvefit.com/index.html?action=openshare&id=7b237893-c52c-49db-bcf6-e29ccf391b7c

但同樣，有締結任何的數據非常少。

來源

2015-09-20 23:46:57

我會盡量計算更多分數，然後謝謝你。 – SrKurtz

這是一個有趣的結果，立方迴歸。但理論上這是一個功率曲線。因此，我選擇了擬合方法，並且低看，它計算出最佳擬合功率曲線，其中a = 4.201811e-7和b = 2.713502，其中R^2 = 0.9999。理論不關心a，並預測b = 2.7095 ...每個OP的維基百科鏈接。所以你去了，看起來非常適合理論價值。 –

@ ErickG.Hagstrom您*的結果*是一個有趣的結果:) –

有沒有辦法讓StoogeSort更加曲線？

回答

相關問題