0 
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²)

请帮忙！确认我是否正确，如果我错了，请纠正我。

4

1 回答 1

2

它看起来像一棵（非必要平衡的）二叉树，其实现方式类似于二叉堆的实现方式——在 i 的子节点为 2i 和 2i+1 的数组中。

应该有人记录下他们做得更好的地方。

我同意你对 fillCol 的评价。

那种可调用的似乎是一个不相关的问题，是的，它确实看起来 O(n^2) 具有正常的数据结构。

于 2012-04-26T23:14:37.863 回答