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²),Linked list 是 O (N³)。
表示图的类使用邻接矩阵来表示顶点之间的连接。包含 N 个节点且每个节点平均有 M 个连接的图的空间要求是多少?
我认为是O(N²)
求助!确认我是否正确,如果我错了请纠正我。
最佳答案
它看起来像一棵(不一定是平衡的)二叉树,其实现方式类似于二叉堆通常的实现方式——在一个数组中,其中 i 的子节点为 2i 和 2i+1。
应该有人记录下他们做得更好的地方。
我同意您对 fillCol 的评价。
可调用排序似乎是一个不相关的问题,是的,它看起来确实具有普通数据结构的 O(n^2)。
关于java - 算法分析和结构识别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10342496/