計算遞歸函數的大O

Question

我有一個方法來檢查一個數組是否是堆。在每次遞歸調用時，我在左側子樹和右側子樹上創建2個新的遞歸調用來遍歷節點並檢查它們的值是否正確。

我想計算這個BigO。我認爲在最壞的情況下，它是O（n），因爲如果它是堆，那麼它永遠不會提前停止，並且需要訪問每個節點。我認爲最好的情況是O（3），當它檢查第一個左側子樹和右側子樹並且兩個都返回false（不是堆）時會發生這種情況。

我的問題是：這個邏輯是否有意義？我認爲它確實如此，但是每當我看到遞歸函數的時間複雜度時，它們似乎總是處於對數時間的某種形式。對於沒有人明確指出的遞歸函數來說，這幾乎就像是神祕的質量。遞歸函數如何經常在對數時間內處理事物？我的上述邏輯有效嗎？

Answer 1

是的它是有道理的。你看到大多數算法取對數時間的原因是因爲它重複了某些事情，並且繼續將範圍除以某個因子。

Answer 2

是的，這是有道理的。 Master Theorem（儘管可以說是最有趣的）的三種情況中只有一種具有對數。