分類樹生長中最優分裂算法的文獻
在ESL的第 9.7 節中，有一段說明分類（或回歸）樹生長過程中拆分的計算時間通常按如下比例縮放在哪裡是預測變量的數量和是樣本數。
一種天真的方法會導致縮放，我還沒有找到任何參考文獻來解釋算法的分割部分的細節以及如何實現一個典型的 縮放。
在樸素方法中，在對觀察值進行初始排序之後，在觀察值之間的中點，並且計算每個分割的損失可以及時完成，比例如下.
我可以（並且可能）研究我知道的一些實現的源代碼，但是參考文獻會很好特別是關於時間複雜度。
我會給出一個不同的答案，因為評論太多了，而且它處理的是更一般的方法。
因此，在 ESL 中，它們確實描述了分支定界的計算時間（更準確地說，它在我看來就像是分而治之）。
我們用觀察次數和當我們長出一棵樹時，子節點的數量。如果我們考慮，我認為我們一般不會鬆懈等待修復。此外，我們可以用在給定節點計算分裂點的處理時間。
因此，我們可以遞歸地編寫執行時間的公式，例如：
我們在這裡考慮子節點拆分輸入數據集的大小在大小相等的子集. 我們知道這是最好的情況。 但是，我們可以看到這是主定理的一個眾所周知的應用。這在CLRS book中有很好的記錄。我有第 3 版，詳細信息在第 4.5 節，證明在下一節。我不太記得細節，但我記得如果擴展遞歸併將一些術語組合在一起，它不會太複雜。
但是，對於這種情況，重要的是何時- 線性時間，算法的結果時間是. 該時間是針對單個輸入變量計算的，因此，我們的總時間為變量將是
如果所有輸入最初都排序在，並且在這個排序的輸入上找到分裂值需要線性時間。在這裡我們可以應用在線方差算法，正如我在之前的回答中提到的. 為了更容易找到中位數。我承認我從未嘗試過其他樹的損失函數。
但是請注意，如果拆分大小相等，則主定理適用於最佳情況。最壞的情況是分裂非常不平衡。在那裡，人們可以應用不同的主定理案例，時間將變為.
作為結論，我假設 ESL 作者通常以用於描述快速排序算法的方式使用該術語。通常快速排序給出運行時間，有最壞的情況, 對於一些特定的數據設置。
我希望它有所幫助。