瞭解從代碼

Question

衍生出來的大O符號我爲一些二叉樹問題編寫了一些代碼...代碼如下，它繼續沿着左邊的樹回答yes，右邊的答案no並返回外部節點，如果它到達一個。

用Java編寫的，

public static int price(BinaryTree<Integer> t, boolean[] p) { 

    Position<Integer> root = t.root(); //1 
    while (t.isInternal(root)) { //2 

     int element = root.element(); // 3 

     if (!p[element]) { //4 
      root = t.getRight(root);//5 
     } 

     if (p[element]) { //6 
      root = t.getLeft(root); //7 
     } 
    } 
    int price = root.element(); //8 
    return price; //9 
} 

在計算大OI認爲最好號碼在評論中碼以上步驟...我也跟着從這裏

Big O, how do you calculate/approximate it?

的例子

因此，上面的1-9應該等同於類似的東西，其中C是常數，???是我的循環（其中N是給定數據結構的輸入數）

C + ??? + C + ??? + C + ??? + C + C + C

我while循環是我認爲C*N或(O(N))相當，但C*N現在）和我的兩個if語句應該是（對於時間索引複雜O(1) ...和O(N)空間的複雜性，我會堅持隨着時間的推移，現在的複雜性）

所以現在我應該（去掉C元素的事業，他們是常數，不真正的問題）

C*N + C + C的時間複雜度

和

C*N + C*N + C*N空間複雜

含義我

C*N或O (N)的時間複雜度和空間複雜度

O(3N)可視爲O(N) .. 。

所以我的問題是，我是否正確地做了這件事，如果不是我哪裏出錯了？

謝謝

編輯：

樹向左移動提供一個真正的（是）回答或右側給出一個否定的。內部節點編號從0到m-1，用於樹中m個內部節點。因此，如果在根，內部節點0處給出no，並且因此向右移動，則該內部節點可能是節點3，因此布爾答案在p [3]而不是p [1]，因爲p [1]是答案對於節點1，即問題1.道歉混淆

Answer 1

是和否。

該算法確實是O(n)，因爲您「觸摸」每個元素的次數不會超過常數。

但是，這不是一個嚴格的限制，換句話說 - 它不是Theta(n)，它是Theta(logN)。 （請記住，大O只是一個上限）。

這是因爲樹是平衡的，並且您的算法基本上從樹中的根到樹葉中獲取路徑。請注意，一旦你「選擇」去左/右，你永遠不會回去。所以基本上你只需在每個高度上「觸摸」一個節點的次數是固定的，這就使得你的算法O(h)-其中h是樹的高度。

因爲樹是平衡的，h < C * log(n)，對於某一常數C - 這使得算法Theta(logN)