标签: space-complexity

在 Big-O 表示法中，O(N) 和 O(2N) 描述了相同的复杂度。也就是说，O(2N)的算法时间或空间复杂度的增长率本质上等于O(N)。尤其是与复杂度为 O(N^2) 的算法（给定极大的 N 值）相比，这一点尤其明显。O(N) 呈线性增加，而 O(N^2) 呈二次方增加。

所以我理解为什么 O(N) 和 O(2N) 被认为是相等的，但我仍然不确定是否将这两者视为完全相等。在输入数量 N 为 100 万或更多的程序中，在我看来，将时间复杂度减半实际上会节省大量时间，因为程序可能会少执行数百万个操作。

我正在考虑一个包含两个 for 循环的程序。每个 for 循环都会迭代一个非常大的 N 个元素数组的整个长度。该程序的复杂度为 O(2N)。O(2N) 减少到 O(N)，但我觉得只需要一个 for 循环而不是两个的实现会使其成为更快的程序（即使单个 for 循环实现为了速度而牺牲了一些功能） ， 例如）。

我的问题：

如果您有一个时间复杂度为 O(2N) 的算法，将其优化为 O(N) 时间复杂度是否会使其速度提高两倍？

换句话说，将 O(2N) 算法优化到 O(N) 是否会带来显着的好处？我想程序的速度会有所增加，或者增加的幅度是否微不足道，以至于不值得付出努力，因为 O(2N) == O(N) ？

一般来说,更具体地说是伯努利混合模型(又名潜类分析).

假设我有一个递归函数，它在具有n节点和高度的完美平衡的二叉树上工作，并log(n)在树的根部调用下面的函数。

void printPaths(TreeNode root, int[] array, int depth){
    if (root == null){
        print array;
    }
    array[depth] = root.data;
    printPaths(root.left, array, depth + 1);
    printPaths(root.right, array, depth + 1);
}

array = new int[depthOfTree]
printPaths(root, array, 0);

让数组为长度log(n)（它将沿树的路径存储值）。我知道递归调用堆栈将是 max height log(n)。我不确定的是 Java 的“按值传递”性质和 Java 垃圾收集如何影响时间和空间复杂性。

1) 将数组传递给递归调用的时间复杂度是多少？如果 Java 是“按值传递”，那么O(log(n))在开始任何函数执行之前，每个递归调用是否都只是简单地复制数组？

2) 任一时刻在内存中浮动的这些数组副本的上限是多少？我的倾向是说O(log(n))。这是否意味着空间复杂度是O(log(n)log(n))？我在一本书中读到“空间复杂度是O(log(n))因为算法会递归O(log(n))次数，并且路径参数O(log(n))在递归过程中只在空间分配一次”。

我只想仔细检查在最坏的情况下Trie数据结构可能具有的总空间。我以为会是O（N * K），其中N是节点总数，K是字母表的大小（指向其他尝试），但是人们一直告诉我这是O（K ^ L），其中K是字母的大小和L是平均单词长度，但是那些空指针会占用Java中的存储空间吗？例如，如果节点之一只有总大小为K的3个分支/点，它是否使用K空间？还是只有3个？以下是Trie的实现Java

class Trie {
     private Trie [] tries;

     public Trie () {
          // A size 256 array of Trie, and they are all null
          this.tries = new Trie[256]; // K = 256;
     }
}

给定n个整数的列表,其中列表中的每个整数都存在两次,除了一个元素,它在列表中存在一次.例如,

[1 3 3 6 2 7 1 2 7]

我需要找到一个线性时间O(n)和一个常量空间O(1)算法,它返回列表中存在一次的元素.在上面的示例中,算法应返回6.请注意,列表不是由任何特定顺序提供的.(列表中元素的顺序是随机的).

我可以使用字典在O(n)线性时间内解决这个问题但不幸的是字典需要O(n)空间.有任何想法吗？

给出以下方法：

public String toString()
{
    if (_head == null)
        return "";
    String S="";
    WordNode currentNode = _head;
    while (currentNode != null)
    {
       S+=currentNode.getWord()+" ";
       currentNode = currentNode.getNext();
    }   
    return S;

}

什么是时间和空间复杂度？在Java中，String是不可变的对象。它如何影响复杂性？谢谢。

任何算法示例我们何时比O(n logn)更喜欢Big O(n ^ 2)时间复杂度？我在某处看到过这个问题,但没有找到答案.

我一直在搜索贝尔曼-福特算法的空间复杂度，但在维基百科贝尔曼-福特算法上，它说空间复杂度是 O(V)。在这个链接上它说 O(V^2) 。我的问题是；什么是真正的空间复杂度，为什么？

我正在寻找上述算法的时间和空间复杂度，但我在谷歌上找不到，我已经浪费了两天多没有任何结果。如果你们能帮助我，我将非常感激。

有人可以提供时间和空间的 O(log(n)) 和 O(nlog(n)) 问题的示例吗？

我对这种类型的分析很陌生，看不到过去的多项式时间/空间。

我不明白的是，你怎么能成为 O(1) < O(log(n)) < O(n) 就像“半常数”一样？

此外，我将不胜感激任何涵盖这些情况（时间和空间）的优秀示例：

我发现空间分析有点模棱两可，因此与同一地点的时间分析中的其他案例相比，看到它会很高兴 - 我无法在网上可靠地找到它。

您能否在空间和时间分析中为每个案例提供示例？