我想知道size()
TreeSet的部分视图的时间复杂度是多少。
假设我要添加随机数来设置(而且我不在乎重复性):
final TreeSet<Integer> tree = new TreeSet<Integer>();
final Random r = new Random();
final int N = 1000;
for ( int i = 0; i < N; i++ ) {
tree.add( r.nextInt() );
}
现在我将size()
呼叫的复杂性理解为:
final int M = 100;
for ( int i = 0; i < M; i++ ) {
final int f = r.nextInt();
final int t = r.nextInt();
System.out.println( tree.headSet( t ).size() );
System.out.println( tree.tailSet( f ).size() );
if ( f > t ) {
System.out.println( tree.subSet( t, f ).size() );
} else {
System.out.println( tree.subSet( f, t ).size() );
}
}
AFAIK的复杂性tree.headSet( t )
,tree.tailSet( f )
并且tree.subSet( f, t )
是O(LG
N),set.size()
是O(1),但对于size()
上述的方法?我感觉很不好,它是O(K),其中K是所选子集的大小。
也许如果有某种变通办法来找到集合中某个元素的索引就足够了,因为如果我可以得到的话ti = indexOf(f)
,可以说O(lg N)恰好是我所需要的。
看起来像size ()
is的复杂性O(N)
,因为它可能调用TreeMap.NavigableSubMap.EntrySetView.size ()
这样实现的对象(Oracle JDK 1.7.0_13):
public int size() {
if (fromStart && toEnd)
return m.size();
if (size == -1 || sizeModCount != m.modCount) {
sizeModCount = m.modCount;
size = 0;
Iterator i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
}
问题内容: 我对未索引数据集上的GroupBy操作的渐近复杂度(大O)感兴趣。最著名的算法的复杂性是什么,SQL Server和LINQ使用的算法的复杂性是什么? 问题答案: 可以对已排序的行(n log(n)复杂度) 进行一次遍历(n复杂度)分组,因此分组的 复杂度为n log(n),其中n是行数。如果group by语句中使用的每个列都有索引,则不需要排序,并且复杂度为n。
假设我有一个有V节点和E边的无向图。如果我用邻接列表表示图形,如果我有x和y之间边的表示,我还必须在邻接列表中有y和x之间边的表示。 我知道有向图的DFS具有VE复杂性。对于无向图,它没有v 2*e复杂性,因为您访问每个边2次?抱歉,如果这是一个愚蠢的问题...我真的很想明白这个想法。谢谢你,
问题内容: 我想在下面学习给定语句的时间复杂度。(在Java8中) 任何想法? 问题答案: 由于时间复杂度取决于所有操作,因此没有通用的答案。由于必须完全处理流,因此必须将其基本时间复杂度乘以每个元素完成的所有操作的成本。假设迭代成本本身并不比差,大多数流源就是这种情况。 因此,假设没有影响时间复杂度的中间操作,则必须评估每个元素的功能,该功能应独立于其他元素,因此不影响时间复杂度(无论它有多昂贵
Redis zrank。 返回存储在key处的排序集中成员的排名,分数从低到高排序。排名(或指数)是基于0的,这意味着得分最低的成员排名为0。 为什么复杂度是O(log(N))?成员按分数排序,但zank按成员查询。 我找到了一些可能是答案的东西。 A.zset由ziplist实现时 大小小于128 每个成员的大小小于64字节 所以,ziplist的大小很小,所以这不是我讨论的问题。 B.当zse
本文向大家介绍SQL中简单视图和复杂视图之间的区别,包括了SQL中简单视图和复杂视图之间的区别的使用技巧和注意事项,需要的朋友参考一下 在讨论简单和复杂之前,首先我们应该知道什么是视图。视图是从一个或多个表创建的逻辑虚拟表,主要可用于一次从一个或多个不同表中获取列。根据视图中涉及的表,我们可以区分SQL中的简单视图和复杂视图。 以下是简单视图和复杂视图之间的重要区别。 序号 键 简单检视 复杂视图
问题内容: 虽然圈复杂度是一个值得衡量的指标,但我倾向于发现它并不是识别难以维护的代码的有效工具。特别是,我倾向于发现它只是突出显示了某些类型的代码(例如解析器),并且错过了困难的递归,线程和耦合问题以及许多已定义的反模式。 还有哪些其他工具可用来识别有问题的Java代码? 注意,我们已经使用了PMD和FindBugs,我认为它们对于方法级问题的识别非常有用。 问题答案: 我的经验是,查看代码可维