时间复杂度和空间复杂度之间的差异？ [英] differences between time complexity and space complexity?

问题描述

我已经看到，在大多数的情况下，时间复杂度相关的空间的复杂性，反之亦然。例如，在一个数组横动

I have seen that in most of the cases the time complexity is related to the space complexity and vice versa. For example in an array traverse:

for i=1 to length(v)
    print (v[i])
endfor

在上述情况下，很容易看出，算法复杂度在时间上是O（n），但我所看到的空间复杂度也是N（能不能再presented为O（n）也？）

in the aforementioned case it is easy to see that the algorithm complexity in terms of time is O(n), but for what I see the space complexity is also n (can it be represented O(n) also?)

我的问题：？是有可能，一个算法具有空间复杂度不同的时间复杂度

推荐答案

在时间和的空间的复杂性并不相互关联的。它们被用于描述的算法将根据所输入的多大的空间/时间

The time and space complexities are not related to each other. They are used to describe how much space/time your algorithm takes based on the input.

• 例如，当算法空格的复杂性：

• O（1） - 恒 - 算法采用的是固定的（小）的空间不依赖于输入。对于输入的每个大小的算法将是相同的（恒定）的空间。这是因为输入的不考虑，重要的是时间/的打印的空间，在你的榜样的情况下命令。
• O（N），为O（n ^ 2）， O（日志（N）） ... - 这些都表明您创建额外的对象，根据您的输入的长度。例如创建的每个对象的副本v 存放在数组中，并在打印的需要 O（n）的后空间创建 N 其他对象。

• 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.

在此相反在时间的复杂性描述你的算法消耗了多少时间根据输入的长度。还是那句话：

In contrast the time complexity describes how much time your algorithm consumes based on the length of the input. Again:

• O（1） - 不管有多大的投入总是需要一定的时间 - 例如只有一条指令。像

功能（表L）{打印（我得到的名单）; }

function(list l) { print("i got a list"); }

• O（N），为O（n ^ 2）， O（日志（N）） - 这又是基于输入的长度。例如

• O(n), O(n^2), O(log(n)) - again it's based on the length of the input. For example

function(list l) {
    for (node in l) {
        print(node);
    }
}

请注意，这两个最后的例子采取 O（1）空间，你不创造任何东西。把它们比作

Note that both last examples take O(1) space as you don't create anything. Compare them to

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

这需要 O（N）的空间，因为你创建一个新的列表，其大小取决于输入线性方式的大小。

which takes O(n) space because you create a new list whose size depends on the size of the input in linear way.

您的示例显示了时间和空间复杂度可能会有所不同。它采用 v.length * print.time 打印所有的元素。但空间始终是相同的 - O（1），因为你没有创建额外的对象。所以，是，它可能是一个算法具有不同的时间和空间复杂度，因为它们不依赖于彼此

Your example shows that time and space complexity might be different. It takes v.length * print.time to print all the elements. But the space is always the same - O(1) because you don't create additional objects. So, yes, it is possible that an algorithm has different time and space complexity, as they are not dependent on each other.

这篇关于时间复杂度和空间复杂度之间的差异？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！