clojure中count函数的时间复杂度是多少？

Question

在clojure中计算的时间复杂度是多少？

Answer 1

这是实施:

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).