问时间复杂性和空间复杂性之间的差异？

EN

时间和空格的复杂性并不是相互关联的。它们用于根据输入来描述算法所需的空间/时间。

• 例如，当算法的空间复杂度为：

- `O(1)` - constant - the algorithm uses a fixed (small) amount of space which doesn't depend on the input. For every size of the input the algorithm will take the same (constant) amount of space. This is the case in your example as the input is not taken into account and what matters is the time/space of the `print` command.
- `O(n)`, `O(n^2)`, `O(log(n))`... - these indicate that you create additional objects based on the length of your input. For example creating a copy of each object of `v` storing it in an array and printing it after that takes `O(n)` space as you create `n` additional objects.

​

• 相反，时间复杂度根据输入的长度描述算法消耗的时间。再一次：

- `O(1)` - no matter how big is the input it always takes a constant time - for example only one instruction. Like

函数(列表l) {打印(“我有一个列表”)；}

- O(n)，O(n^2)，O(log(n)) --同样是基于输入的长度。例如

函数(列表l) { for (节点in l) {print(节点)；}}

​

请注意，最后两个示例都使用O(1)空间，因为您没有创建任何内容。把它们与

function(list l) {
    list c;
    for (node in l) {
        c.add(node);
    }
}

这占用了O(n)空间，因为您创建了一个新列表，其大小取决于线性输入的大小。

您的示例显示，时间和空间的复杂性可能有所不同。需要v.length * print.time打印所有元素。但是空间总是相同的- O(1)，因为您不创建额外的对象。因此，是的，有可能一个算法具有不同的时间和空间复杂度，因为它们不相互依赖。

时间和空间复杂度是计算算法效率的不同方面。

时间复杂度负责了解算法的计算时间随着输入大小的变化而变化。 另一方面，空间复杂度处理的是，随着输入大小的变化，该算法需要多少(额外)空间。

要计算算法的时间复杂度，最好的方法是检查输入的大小是否增加，比较的次数(或计算步骤)是否也会增加，而计算空间复杂度最好的方法是看到算法的额外内存需求也随输入大小的变化而变化。

一个很好的例子可以是气泡分类。

假设您尝试对一个由5个元素组成的数组进行排序。在第一遍中，您将比较第一个元素和接下来的4个元素。在第二关，你将比较第二个元素和接下来的3个元素，你将继续这个过程，直到你完全用尽列表。

现在，如果您尝试对10个元素进行排序，会发生什么。在这种情况下，您将首先比较第一个元素和接下来的9个元素，然后再将第二个元素与接下来的8个元素进行比较，等等。换句话说，如果您有N个元素数组，那么首先将第一个元素与N-1元素进行比较，然后将第二个元素与N-2元素进行比较，等等。这会导致O(N^2)时间复杂性。

但尺寸呢。在对5个元素或10个元素数组进行排序时，是否使用了任何额外的缓冲区或内存空间。您可能会说是，我确实使用了一个临时变量来进行交换。但是，当数组的大小从5增加到10时，变量的数量是否发生了变化。不，不管输入的大小如何，您总是使用单个变量进行交换。这意味着输入的大小与您需要的额外空间无关，这会导致O(1)或恒定的空间复杂性。

现在作为一个练习，研究合并排序的时间和空间复杂性。

首先，这个循环的空间复杂度是O(1) (在计算算法所需的存储量时，通常不包括输入)。

所以我要问的问题是，一个算法的时间复杂度是否可能与空间复杂度不同？

是的，是这样的。一般情况下，算法的时间和空间复杂度是不相关的。

有时，一种可能会增加，而另一种则会牺牲。这叫做时空权衡。