Tag: 时间复杂度

这个for循环的大O分析

sum = 0; for (i = 1; i <= n; i++) { //#1 for (j = 1; j <= i * i; j++) { //#2 if (j % i == 0) { //#3 for (k = 1; k <= j; k++) { //#4 sum++; } } } } 以上让我感到困惑 Suppose #1 runs for N times […]

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

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

用于计算Java代码的大O时间复杂度的工具？

我有一个关于Java软件的时间复杂度（大O表示法）的问题。 有没有办法快速计算或测试它（或任何可以为我计算它的网站将受到欢迎）。 例如，我想检查以下代码片段，并可能改进： int dcount = 24423567; int a = 0; if (dcount == 0){ a = 1; } String ds = Integer.toString(dcount); String[] sa = ds.split(“(?<=.)"); HashSet hs = new HashSet(); Collections.addAll(hs, sa); a = hs.size(); if (dcount < 0) a–; System.out.println(a);

java.util.Collections.sort（）方法的时间复杂度是多少？

我写了以下课程： public class SortingObjectsWithAngleField implements Comparator { public int compare(Point p1, Point p2) { double delta = p1.getAngle() – p2.getAngle(); if(delta == 0.00001) return 0; return (delta > 0.00001) ? 1 : -1; } } 然后，在我的main()方法中，我创建了一个List ，我添加了一些具有“X”和“angle”字段的对象。 然后我用： Collections.sort(list, new SortingObjectsWithAngleField()); 这种排序方法的复杂性是什么？

递归斐波那契算法的空间复杂度是多少？

这是Cracking the Coding Interview（第5版）中Fibonacci序列的递归实现 int fibonacci(int i) { if(i == 0) return 0; if(i == 1) return 1; return fibonacci(i-1) + fibonaci(i-2); } 在观看关于该算法的时间复杂度的video后， 斐波纳契时间复杂度 ，我现在理解为什么该算法在O（2 n ）中运行。 然而，我正在努力分析空间复杂性。 我在网上看了一下这个问题。 在这个Quora线程中，作者声明“在你的情况下，你有n个堆栈帧f（n），f（n-1），f（n-2），…，f（1）和O（1 ）“。 你不会有2n堆栈帧吗？ 说f（n-2）一帧将用于实际的呼叫f（n-2），但不会有来自f（n-1）的呼叫f（n-2）？

HashMap方法的时间复杂度

由于我正在研究时间复杂性，我一直在搜索oracle Java类库，以了解列表，地图和类中使用的一些标准方法的时间复杂性。 （更具体地说，ArrayList，HashSet和HashMap） 现在，在查看HashMap javadoc页面时 ，他们只是真正谈论get()和put()方法。 我仍然需要知道的方法是： remove(Object o) size() values() 我认为remove()将与get() ， O(1)具有相同的复杂性，假设我们没有具有相同hashCodes的巨型HashMap等等…… 对于size()我还假设为O(1) ，因为HashSet（也没有顺序size()具有复杂度为O(1)的size()方法。 我不知道的是values() – 我不确定这个方法是否会以某种方式“复制”HashMap，给出O(1)的时间复杂度，或者它是否必须迭代HashMap，使复杂性等于HashMap中存储的元素数量。 谢谢。

C ++和Java中的字符串连接复杂性

考虑这段代码： public String joinWords(String[] words) { String sentence = “”; for(String w : words) { sentence = sentence + w; } return sentence; } 在每个连接上创建字符串的新副本，以便总体复杂度为O(n^2) 。 幸运的是，在Java中，我们可以使用StringBuffer来解决这个问题，每个附加都有O(1)复杂度，然后总体复杂度为O(n) 。 在C ++中， std::string::append()具有O(n)的复杂性，我不清楚stringstream的复杂性。 在C ++中， StringBuffer方法是否具有相同的复杂性？

从排序数组中查找小于O（n）的唯一数字

我接受了采访，有以下问题： 在小于O（n）的时间内从排序的数组中查找唯一的数字。 Ex: 1 1 1 5 5 5 9 10 10 Output: 1 5 9 10 我给出了解决方案，但那是O（n）。 编辑：排序的数组大小约为200亿，唯一数字约为1000。

System.arraycopy（…）的时间复杂度？

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)是一种本机方法。 这种方法的时间复杂度是多少？

Java中的LRU缓存，具有generics和O（1）操作

这是一个在求职面试中出现的问题。 我们的想法是定义一个数据结构，而不是使用Java内置的LinkedHashMap。 LRU高速缓存删除最近最少使用的条目以插入新条目。 因此，给出以下场景： A – B – C – D – E 如果A是最近最少使用的项目，如果我们要插入F，我们需要删除A. 如果我们通过（键，值）保存带有缓存条目的HashMap和包含元素的键和使用时间的单独列表，则可以很容易地实现这一点。 但是，我们需要查询列表以找到最近最少使用的项目，具有潜在的O（n）时间复杂度。 如何在Java中为通用对象和O（1）操作实现此结构？ 这与可能的重复不同，因为它侧重于效率（O（1）ops）和实现数据结构本身，而不是扩展Java。