Tag: big o

mergeSort实现，用于查找尝试从文件读取时无效的反转次数: 我试图做一个mergesort实现来查找反转次数。。该数组似乎返回了一个硬编码的小数字列表的正确结果，但是当我从文件中读取时返回的数字不正确。我猜它与字符串整数比较有关，但无法弄清楚究竟是什么问题，。任何见解都会有所帮助。这是（相关）代码 – public class ReadFile { public static void main(String args[]){ int count=0; int n[]; int i=0; try{ n=OpenFile(); int num[] = new int[n.length]; for (i=0;i<n.length;i++){ num[i]=n[i]; // System.out.println( "Num"+num[i]); } count=countInversions(num); } catch(IOException e){ e.printStackTrace(); } System.out.println(" The number of inversions"+count); } public static int [] OpenFile()throws IOException{ FileReader fr=new […]

具有if语句的嵌套循环的时间复杂度O（N）：O（N ^ 4）？: 我试图找出这个片段的big-O方面的严格限制： for(int i = 1 ; i <= n ; i++) { for(int j = 1; j <= i*i ; j++) { if (j% i == 0){ for(int k = 0 ; k<j ; k++ ) sum++; } } } 如果我们从最内层循环开始，它将在最坏的情况下运行k = n ^ 2次，这占O（N ^ 2）。每次j = m * i时，if语句都为真，其中m是任意常数。由于j从1运行到i ^ 2，这将在m […]

LinkedList如何添加（int，E）O（1）复杂度？: 从链表标签维基摘录：链表是一种数据结构，其中元素包含对下一个（以及可选的前一个）元素的引用。链接列表提供在任何位置的O（1）插入和移除，O（1）列表串联，以及前（和可选后）位置的O（1）访问以及下一元素访问的O（1）。随机访问具有O（N）复杂性并且通常是未实现的。（强调我的）我很惊讶地读到这一点 – 如何将列表插入一个复杂度低于简单读取索引的随机索引？所以我查看了java.util.LinkedList的源代码。 add(int, E)方法是： public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } addBefore(E, Entry方法只是指针重新分配，但也有entry(int)方法： if (index = size) throw new IndexOutOfBoundsException(“Index: “+index+ “, Size: “+size); Entry e = header; if (index > 1)) { for (int i = 0; […]

为什么不是LinkedList.Clear（）O（1）: 我假设LinkedList.Clear（）在我正在处理的项目上是O（1），因为我使用LinkedList来消耗我需要高吞吐量的清除和重新使用LinkedList的消费者中的BlockingQueue。事实certificate这个假设是错误的，因为（OpenJDK）代码这样做： Entry e = header.next; while (e != header) { Entry next = e.next; e.next = e.previous = null; e.element = null; e = next; } 这有点令人惊讶，有没有什么好的理由LinkedList.Clear不能简单地“忘记”它的header.next和header.previous成员？

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)

3个嵌套循环的大O.: 另一个大O符号问题…对于代码的大O是什么： for (int i = n; i > 0; i = i / 2){ for (int j = 0; j < n; j++){ for (int k = 0; k < n; k++){ count++; } } } 我的想法：所以打破它，我认为外部循环是O(log2(n)) ，然后每个内部循环是O(n) ，这将导致O(n^2 * log2(n))问题＃ 1是正确的吗？问题2：当组合嵌套循环时，它总是像每个循环的大O一样简单吗？

Java HashMap如何为“get”操作执行常量时间查找O（1）？: 我理解HashMap如何工作的基础知识 – hm.put（obj）根据obj.hashCode值找到放置对象的正确存储桶。然后在该桶内如果另一个对象.equals（obj）然后替换它，如果没有将它添加到桶中。但我不清楚HashMap.put和HashMap.get如何可以是常数时间O（1）。根据我的理解，桶的数量应该基于哈希码，因此将100个对象放入哈希映射将（大致）创建100个桶（我知道有时会在哈希码中发生冲突，所以它可能少于100但不是经常）。因此，随着添加到散列映射的对象数量的增加，桶的数量也增加 – 并且因为冲突很少，所以这并不意味着桶的数量几乎与添加的对象数量线性增长，在这种情况下是HashMap。 put / HashMap.get将是O（n），因为它必须在找到正确的桶之前搜索每个桶。我错过了什么？

获取在log（n）时间内落在特定范围内的排序数组中的元素数: 假设我有一个由y按升序排序的以下类的数组： public class Obj { public int x; public int y; } 如何在log（N）时间内找到y值在最小值和最大值范围内的数组中Obj项的数量？我已经考虑过使用二进制搜索来找到带有binarySearch和减法的min和max元素的位置，但是因为它搜索了两次所以不会是2 log（n）吗？ public static int getNumberOfItems(Obj[] a, int min, int max) {

apache poi excel大自动列宽: 我尝试使用Apache poi最新创建一个包含30列和100万条记录的大型excel 2010。我正在创建此链接中的描述http://svn.apache.org/repos/asf/poi/trunk/src/examples/src/org/apache/poi/xssf/usermodel/examples/BigGridDemo.java 。但我希望列宽与列标题文本大小相同。但是在使用以下代码创建excel之后我正在执行此操作 for (int x = 0; x < sheet.getRow(0).getPhysicalNumberOfCells(); x++) { sheet.setColumnWidth(x, 20*256); } 它占用了大量的时间，即使有5GB的堆大小，我也会失去记忆。谢谢内存

有效确定矩阵中元素的算法: 这是一个关于课程作业的问题，所以宁愿你没有完全回答这个问题，而是提出改进我当前算法的运行时复杂性的技巧。我收到了以下信息：函数g（n）由g（n）= f（n，n）给出，其中f可以递归地定义我用以下代码递归地实现了这个算法： public static double f(int i, int j) { if (i == 0 && j == 0) { return 0; } if (i ==0 || j == 0) { return 1; } return ((f(i-1, j)) + (f(i-1, j-1)) + (f(i, j-1)))/3; } 这个算法给出了我正在寻找的结果，但效率极低，我现在的任务是改善运行时的复杂性。我写了一个算法来创建一个n * n矩阵，然后计算每个元素直到[n] [n]元素，然后它返回[n] [n]元素，例如f（1,1）返回0.6重复出现。 [n] [n]元素重复为0.6，因为它是（1 + […]