java算法分析与结构识别
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;}
}
以数据结构为例。这是怎么一回事?我认为这是一个二叉搜索树,但我很确定这是一个最大堆。不过,我主要是学习英国理工学院
public void fillCol (int n, Collection<Integer> col){
for(int i = 0; i < n; i++)
col.add (i);
}
如果是一个链接列表,那么它是什么?我想是O(N)
这是一棵树吗?我想是O(N logn)
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²)
请帮忙!确认我是否正确,或者纠正我的错误
# 1 楼答案
它看起来像一个(不一定是平衡的)二叉树,实现方式类似于二叉堆通常的实现方式——在一个数组中,i的子元素是2i和2i+1
应该有人记录下他们做得更好的地方
我同意你对菲尔科尔的评价
排序可调用似乎是一个不相关的问题,是的,它看起来确实是O(n^2),具有正常的数据结构