瞭解大O符號 - 破解編碼訪談示例9

Question

我被這兩個代碼卡住了。

代碼1

int f(int n){ 
    if (n <= 1){ 
     return 1; 
    } 
    return f(n-1) + f(n-1); 
} 

代碼2（平衡二叉搜索樹）

int sum(Node node){ 
    if(node == null){ 
     return 0; 
    } 
    return sum(node.left) + node.value + sum(node.right); 
} 

作者說代碼1的運行時間爲O（2^n）和空間複雜度是O（n）

並且代碼2是O（N）

我不知道這兩個代碼有什麼不同。看起來兩者是相同的二叉樹

Answer 1

那麼有一個錯誤，因爲第一個片段運行在O（2^n）而不是O（n^2）。

的解釋是： 在我們遞減n但創造的呼叫數量的兩倍的每一步，所以對於n我們以f調用兩次（N-1）和N-1，我們的電話的每一個我們會用f（n-2）調用兩次 - 這是4次調用，如果我們再去一次調用，我們會用f（n-3）調用8次：所以調用的次數是：2^1 ，然後2^2，然後2^3，2^4，...，2^n。

第二個片段在二叉樹上進行一次傳遞並且到達每個節點一次，所以它是O（n）。

Answer 2

代碼1：

的if()語句運行按照無論是傳入的參數，但該函數調用自身n-1倍n倍。爲了簡化：

n * (n-1) = n^2 - n = O(n^2 - n) = O(n^2)

代碼2：

搜索遍歷樹的每一個元素只有一次，函數本身不具有任何for()。由於有n項目，他們只被訪問一次，它是O(n)。

Answer 3

第一個代碼的確是O(2^n)。

但是第二個代碼不能是O(n)，因爲那裏沒有n。這是許多人遺忘的事情，通常他們假設什麼n是沒有澄清它。

事實上，你可以根據任何事情來估計任何東西的增長速度。有時它是輸入的大小（在第一個代碼中是O(1)或O(log n)，具體取決於大數字的用法），有時只是參數（如果是數字）。

因此，當我們開始考慮第二個代碼什麼時間和內存取決於我們能得到這些東西：

1. time=O(number_of_nodes_in_tree)
2. time=O(2^height_of_tree)
3. additional_space=O(height_of_tree)
4. additional_space=O(log(number_of_nodes))（如果樹平衡）

全部o如果他們在同一時間是正確的 - 他們只是把事情聯繫到不同的事情上。

Answer 4

首先，瞭解N在兩種情況下都很重要。 在第一個示例中，它非常明顯，因爲您直接在代碼中看到它。對於第一種情況，如果您構建f(i)調用樹，則會看到它包含O(2^N)元素。確實，

  f(N)    // 1 node 
     /  \ 
    f(N-1)   f(N-1)  // 2 nodes 
/ \ / \ 
f(N-2) f(N-2) f(N-2) f(N-2) // 2^2 nodes 
... 
f(1) ........ f(1)   // 2^(N-1) nodes 

在第二種情況下，N是（很可能）樹中的元素的數量。正如你從代碼中看到的那樣，我們遍歷每一個元素只有一次 - 當你看到每個樹節點調用一次node.value時，你可能會意識到它。因此O（N）。

注意，在這種任務ň通常意味着輸入的大小，而什麼輸入是取決於你的問題。它可以只是一個數字（比如在你的第一個問題中），一維數組，二叉樹（就像在你的第二個問題中），或者甚至是一個矩陣（儘管在後一種情況下，你可能會看到明確的陳述如「一個大小爲M * N「的矩陣）。

所以你的困惑可能來自這個事實，即「N的定義」在這兩個問題之間是不同的。換句話說，我可能會說n2 = 2^n1。