clojure中count函数的时间复杂度是多少?
答
这里的实现:
public static int count(Object o){
if(o == null)
return 0;
else if(o instanceof Counted)
return ((Counted) o).count();
else if(o instanceof IPersistentCollection) {
ISeq s = seq(o);
o = null;
int i = 0;
for(; s != null; s = s.next()) {
if(s instanceof Counted)
return i + s.count();
i++;
}
return i;
}
else if(o instanceof String)
return ((String) o).length();
else if(o instanceof Collection)
return ((Collection) o).size();
else if(o instanceof Map)
return ((Map) o).size();
else if(o.getClass().isArray())
return Array.getLength(o);
throw new UnsupportedOperationException("count not supported on this type: " + o.getClass().getSimpleName());
}
所以它的O(1)对于数组,字符串,集合,实现算地图和任何东西。对于实现IPersistentCollection但没有计算的任何事物,它都是O(n)。