Tag: 时间复杂度

解释时间复杂性？: 如何在N和Big-O中找到给定算法的时间复杂度？例如， //One iteration of the parameter – n is the basic variable void setUpperTriangular (int intMatrix[0,…,n-1][0,…,n-1]) { for (int i=1; i<n; i++) { //Time Complexity {1 + (n+1) + n} = {2n + 2} for (int j=0; j<i; j++) { //Time Complexity {1 + (n+1) + n} = {2n + 2} intMatrix[i][j] = 0; […]

Fibonacci算法的时间复杂度: 所以，我在Java中有一个递归方法来获得’第n个斐波纳契数 – 我唯一的问题是：时间复杂度是多少？我认为这是O（2 ^ n），但我可能弄错了？（我知道迭代更好，但这是一个练习） public int fibonacciRecursive(int n) { if(n == 1 || n == 2) return 1; else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1); }

排序时间总是与第一次排序不同: 我写了几个排序算法。我想比较他们的排序时间，至少差不多。但是在第一次循环之后，所有排序时间都会减少，除了StoogeSort。我认为在背景上有所优化，但我应该考虑采取哪些措施？第一个还是其他？为什么会发生这种情况？ public static void main(String[] args) { RandomNumber rn = new RandomNumber(); Scanner sc = new Scanner(System.in); while(true){ System.out.println(“Enter the input size.”); int n = sc.nextInt(); int[] experimentalArray = rn.experimentalArrayGenerator(n); Stopwatch sw1 = new Stopwatch(); StoogeSort ss = new StoogeSort(experimentalArray.clone()); System.out.println(“StoogeSort : ” + sw1.elapsedTime() + ” µs”); Stopwatch sw2 […]

具有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 […]

算法的复杂性: 我正在学习考试，看到了这个问题，所以我做了以下，是不是正确的？ while循环运行在O（log3n）。 for循环运行在大约O（（n-（某些数学））* log2n）因为我有一个线性的减号，我说整个方法运行在O（nlogn），除非我错了，它是就像是 O（（n-（n / log3n））* log2n）< – 不完全但很完全，无法弄明白。这里是负线性还是不？如果不是什么是正确的bigO？ public void foo (int n, int m) { int i = m; while (i>100) i = i/3; for (int k=i; k>=0; k–) { for (int j=1; j<n; j*=2) System.out.print(k + "\t" + j); System.out.println(); } }

java：基于array2排序array1: 感谢Zirak的帮助在我之前的post中，我在JavaScript中实现了以下内容： var arr1 =[0,1,2,3]; var arr2 =[“ac”, “bc”, “ad”, “e”]; var result = arr1 .sort(function(i, j){return arr2[i].localeCompare(arr2[j])}) document.write(result ); 实现这一点的方法在JavaScript中非常紧凑，这样的简单实现也可以实现这一点的java实现吗？我只能想到实现Comparable接口，如下所示： public class testCompare { public static String[] arr2={“ac”, “bc”, “ad”, “e”}; public static Obj[] arr1={new Obj(0), new Obj(1), new Obj(2), new Obj(3)}; static class Obj implements Comparable{ int index=0; public Obj(int i){ index=i; } […]

找到数组中最长的连续体，连续体中的值之和等于零模3: 我写了一个代码，找到数组中最长的连续体，连续体中的值之和等于零模3，例如对于数组a[]={2,-3,5,7,-20,7} 我们有2-3 + 5 + 7-20 = -9所以输出是5，我的问题是复杂性，现在它是O(n^3)一只小鸟低声说我可以在O(n) public class mmn { public static void main(String[] args) { int a[]={2,-3,5,7,-20,7}; int r=what(a); System.out.println(r); } private static int f(int[]a,int low, int high) { int res=0; for (int i=low;i<=high;i++) res+=a[i]; return res; } public static int what(int[]a) { int temp=0; for(int i=0;i<a.length;i++) { for (int j=i;jtemp) […]

在两个列表之间进行“包含”的有效方法: 我有2个整数列表， l1 = new ArrayList(); l2 = new ArrayList(); 我想找出两者中的重复项目，我有我惯常的做法： – for (Integer i : l1) { if(l2.contains(i)){ System.out.println(“Found!”); } } 我听说contains()是O(n) ，使我的实现O(n^2) 。有没有更好的方法来做到这一点，（少于O(n^2) ）？

二叉树O（n）的InOrder树遍历的时间复杂度？: public void iterativePreorder(Node root) { Stack nodes = new Stack(); nodes.push(root); Node currentNode; while (!nodes.isEmpty()) { currentNode = nodes.pop(); Node right = currentNode.right(); if (right != null) { nodes.push(right); } Node left = currentNode.left(); if (left != null) { nodes.push(left); } System.out.println(“Node data: “+currentNode.data); } } 资料来源：Wiki Tree Traversal 时间复杂度是O（n）吗？如果使用递归完成，时间复杂度是否会相同？新问题：如果我使用上面的代码从TreeA中找到某个节点来创建另一个树TreeB，它将拥有与TreeA一样多的节点，那么创建TreeB的复杂性将是O（n ^ 2），因为它是n个节点和每个节点都会使用上面的代码，即O（n）？

Java中设置的时间复杂度: 有人能告诉我下面代码的时间复杂度吗？ a是一个int数组。 Set set = new HashSet(); for (int i = 0; i < a.length; i++) { if (set.contains(arr[i])) { System.out.println("Hello"); } set.add(arr[i]); } 我认为它是O（n），但我不确定，因为它使用Set ，这也包含方法。它还调用set的add方法。任何人都可以确认并解释上述代码的时间复杂度是多少？还需要多少空间？