Tag: 复杂性理论

Java中TreeSet操作的计算复杂性？

我试图澄清一些关于TreeSet的一些操作的复杂性的事情。 在javadoc上它说： “这种实现为基本操作（添加，删除和包含）提供了有保证的log（n）时间成本。” 到现在为止还挺好。 我的问题是在addAll（），removeAll（）等上发生了什么。这里的Set的javadoc说： “如果指定的集合也是一个集合，则addAll操作会有效地修改此集合，使其值为两个集合的并集。” 它只是解释了操作的逻辑结果还是暗示了复杂性？ 我的意思是，如果两个集合由例如红黑树代表，那么以某种方式加入树木比将“一个”的每个元素“添加”到另一个更好。 在任何情况下，有没有办法将两个TreeSet合并为一个具有O（logn）复杂度的TreeSet？ 先谢谢你。 🙂

Java Big O表示3嵌套循环的log（n）

对于以下嵌套循环，Big O表示法会是什么？ for (int i = n; i > 0; i = i / 2){ for (int j = n; j > 0; j = j / 2){ for (int k = n; k > 0; k = k / 2){ count++; } } } 我的想法是：每个循环都是O(log2(n))所以它就像乘法一样简单 O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3)

Java中TreeSet部分视图的size（）复杂度是多少

我想知道TreeSet的部分视图的size()的时间复杂度是多少。 假设我要添加随机数来设置（我不关心重复）： final TreeSet tree = new TreeSet(); 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 t ) { System.out.println( tree.subSet( t, f […]

用于测量Java代码的经验计算复杂性的工具？

我有一些Java代码，我希望测量经验计算的复杂性。 有一个trend-prof工具，它作为输入编译的C/C++程序。 趋势教程是否有类似的工具作为输入编译的Java程序？

使用二进制堆的多个数组合并

给定k个整数的整数数组，每个整数包含一个未知的正数元素（每个数组中的元素数量不一定相同），其中所有k个数组中的元素总数为n，给出一个合并k个数组的算法单个排序数组，包含所有n个元素。 该算法的最坏情况时间复杂度应为O（n∙log k）。

代码复杂性分析工具超越了圈复杂性

虽然圈复杂度是一个值得衡量的指标，但我倾向于发现它是识别难以维护的代码的糟糕工具。 特别是，我倾向于发现它只是突出显示某些类型的代码（例如解析器），并且错过了难以递归，线程和耦合问题以及许多已经定义的反模式。 还有哪些其他工具可用于识别有问题的Java代码？ 注意，我们已经使用了PMD和FindBugs，我相信这对于方法级问题识别非常有用。

优先级队列消除了复杂性时间

Java中Priority Queue类的remove()函数的复杂性（大哦）是多少？ 我无法在任何地方找到任何记录，我认为它是O（n），考虑到你必须在删除它之前找到该元素然后重新洗牌。 但我看到其他人不同意并认为它是O（logn）。 有任何想法吗？

java中 .length的时间复杂度或隐藏成本

我在java中查看一个项目，发现了一个for循环，如下所示： for(int i=1; i<a.length; i++) { ……….. ……….. ……….. } 我的问题是：计算a.length （这里是数组名称）是否代价高昂？ 如果没有那么a.length是如何在内部计算的（意味着JVM如何确保O（1）访问它）？ 是类似于： int length = a.length; for(int i=1; i<length; i++) { ……….. ……….. ……….. } 就像访问函数内部的局部变量值一样。 谢谢。

这段简单代码的复杂性是什么？

我正在从我的电子书中粘贴这个文本。 它说O（n 2 ）的复杂性，并给出了解释，但我没有看到如何。 问题：此代码的运行时间是多少？ public String makeSentence(String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) sentence.append(w); return sentence.toString(); } 这本书的答案是： O（n 2 ），其中n是句子中的字母数。 原因如下：每次将一个字符串附加到句子上时，您都会创建一个句子副本并遍历句子中的所有字母以将它们复制过来如果您必须在循环中每次迭代最多n个字符，那么您就是循环至少n次，这给你一个O（n 2 ）运行时间。 哎哟! 有人可以更清楚地解释这个答案吗？

Java：声明一个大小为n的数组的大时间是什么？

在Java中声明大小为n的数组的运行时间是多少？ 我想这将取决于内存是否在垃圾收集（在这种情况下可能是O（1））或初始化（在这种情况下它必须是O（n））归零。