算法分析和結構識別

public class Structure <E extends Comparable<? super E>>{ 
    private E[] d; 

    public Structure() { d = getArray(1); } 

    public void show() { show(0); } 

    private void show(int p){ 
    if(p < d.length && d[p] != null) { 
     show(r(p)); 
     show(l(p)); 
     System.out.print(d[p] + " "); 
    } 
    } 
    public void add(E obj) { 
    int p = getPos(obj); 
    if(p >= d.length) 
     resize(); 
    d[p] = obj; 
    } 

    public boolean present(E obj){ 
    int p = getPos(obj); 
    return p < d.length && d[p] != null; 
    } 

    private int getPos(E obj){ 
    int p = 0; 
    while(p < d.length && d[p] != null){ 
     int dir = <*1>; 
     if(dir < 0) 
     p = l(p); 
     else if(dir >0) 
     p = r(p); 
     else 
     return p; 
    } 
    return p; 
    } 
    private E[] getArray(int size) { 
    return (E[]) new Comparable[size]; 
    } 

    private void resize(){ 
    E[] temp = getArray(d.length*2 + 1); 
    for(int i = 0; i < d.length; i++) 
     temp[i] = d[i]; 
    d = temp; 
    } 

    private int l(int i) { return 2 * i + 1;} 
    private int r(int i) { return 2 * i + 2;} 
}

取這個數據結構。它是什麼？我認爲這是一個二叉搜索樹，但我很確定這是一個或一個最大的堆。不過，我主要傾向於BST。算法分析和結構識別

public void fillCol (int n, Collection<Integer> col){ 
    for(int i = 0; i < n; i++) 
    col.add (i); 
}

如果col是鏈接列表，那麼該方法的大O是什麼？我認爲這是O（N）。

和col樹集？我認爲它是O（N log N）。

public void sort (List<Double> data){ 
    int lim = data.size(); 
    for(int i = 0; i < lim; i++){ 
    int m = i; 
    for(int j = i + 1; j < lim; j++) 
     if(data.get(j) < data.get(m)) 
     m = j; 
    data.set(i, data.set(m, data.get(i))); 
    } 
}

和大o爲每種類型的列表。我認爲ArrayList爲O（N²），鏈接列表爲O（N³）。

表示圖的類使用鄰接矩陣來表示頂點之間的連接。對於包含N個節點且每個節點平均有M個連接的圖，空間要求是多少？

我認爲這是O（N²）

請幫忙！確認我是對的，還是糾正我，如果我錯了。

來源

2012-04-26 user1359871

'int dir = <*1>'是什麼意思？ – 2012-04-27 16:22:30

它看起來像一個（不一定是平衡的）二叉樹，其實現方式類似於一個二進制堆經常完成 - 在一個數組中，其中我的孩子是2i和2i + 1。

有人應該記錄他們做得更好。

我同意您對fillCol的評估。

這種可調用看起來像一個無關的問題，是的，它看起來像一個正常的數據結構O（n^2）。

來源

2012-04-26 23:14:37 user1277476

算法分析和結構識別

回答

相關問題