Java - 变量的空间复杂度

这里的空间复杂度是否为O（n）？因为如果k增加5，我的变量p也会增加5.Java - 变量的空间复杂度

所有这种方法现在所做的就是让节点在k处。例如：1-> 5-> 3，当k = 2时，该节点是5

public ListNode reverseKGroup(ListNode head, int k) { 
    int p = 1; 

    while (p < k) { 
     if (head.next == null) { 
      return head; 
     } 
     head = head.next; 
     p++; 
    } 

    return head 
}

来源

2017-07-19 Theo

严格考虑你的算法，它具有空间复杂度O（1）。你的输入是一个列表头和一个数字k，但是你的算法不会消耗任何空间，而不仅仅是参考head和数字p。在我看来，现有的列表不属于你的方法的复杂性。但是，你的时间复杂度是O（N）。

---答案西奥在评论的问题：

p是一个数字（在这种情况下，原始的int类型的，所以它需要4个字节 - 大小不变）。如果p增加，这并不意味着，它需要更多的空间，但存储更高的数字。 p = 5意味着设置了以下字节：“0,0,0,5”，对于p = 257，字节设置为“0,0,1,2”。我认为，JVM以big endian字节顺序存储日期，因此第一个零代表较大的字节。随着小端，字节顺序将被颠倒。

当然，你是对的，对于非常大的N，32位长整数是不够的。因此，严格考虑这个事实，需要O（log（N））位来存储数字，最大为N。例如数字2^186需要存储187位（一个1和186个零）。

但实际上，在处理“通常”数据时，您不会期待如此巨大的数量。由于只有超过32位寄存器（一个int数字），您将需要有2^32个数据条目（1条目= 4个字节用于下一个参考，至少4个字节用于参考值Object，并且对象大小本身=至少8个字节），即2^35个字节= 32个千兆字节。因此，当使用数字时，通常认为它是恒定的空间复杂度。这取决于任务和情况。

来源

2017-07-19 23:22:19 fairtrax

我了解时间复杂度部分。对于空间复杂性，我知道使用头部不占用任何空间。但是，你能解释一下如何使用数字p不占用空间吗？因为如果我增加k，不会增加相同的数量，因此我的算法需要空间输入k，这是O（n）空间复杂 – Theo

@Theo - 我的答案有点长，请参阅编辑的文章。 – fairtrax

非常感谢！ – Theo

根据是否考虑您的空间复杂度的预先存在的结构部分，所述空间复杂度是O（ 1）或O（N），其中N是正在操作的列表的长度，因为您不添加任何新节点并且仅引用现有节点。

k只对时间复杂性很重要。

来源

2017-07-19 23:15:04 nameless

该算法使用的唯一空间是int p的空间，无论输入如何，空间复杂度都是O（1）。时间复杂度确实是O（N）。

来源

2017-07-19 23:23:59 NickL

Java - 变量的空间复杂度

回答

相关问题