アルゴリズム解析と構造識別

Question

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）だと思う。

そして、1つのツリーが設定されていますか？私はそれが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²）、Linkedリストの場合はO（N³）だと思います。

グラフを表すクラスは、隣接行列を使用して頂点間の接続を表します。ノードあたり平均M個の接続を持つN個のノードを含むグラフの領域要件はいくらですか？

私はそれを助けてくださいO（N²）

だと思います！私が正しいかどうかを確認するか、間違っている場合は私を修正してください。

Answer 1

iの子が2iと2i + 1の配列の中で、バイナリヒープがよく行われる方法と同様の方法で実装された（必ずしもバランスのとれた）バイナリツリーのように見えません。

誰かが彼らがうまくやっていたことを文書化しているはずです。

私はあなたのfillColの評価に同意します。

ソート可能な呼び出し可能なものは無関係な質問のように見えます。はい、通常のデータ構造でO（n^2）のように見えます。