Java

Question

这里的 space 复杂度是 O(n) 吗？因为如果 k 增加 5，我的变量 p 也会增加 5。

这个方法现在所做的就是获取 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
}

Answer 1

根据您是否将预先存在的结构视为 space 复杂度的一部分，space 复杂度为 O(1) 或 O(N)，其中 N 是列表的长度正在运行，因为您不添加任何新节点并且仅引用现有节点。

k 只对时间复杂度有影响。

Answer 2

严格考虑您的算法，它的复杂度为 space O(1)。您的输入是列表的 header 和数字 k，但您的算法不会消耗任何 space，而不仅仅是参考 head 和数字 [=12] =].在我看来，现有列表不属于您方法的复杂性。但是，你的时间复杂度是 O(N)。

--- 在评论中回答 Theo 的问题：

p 是一个数字（在本例中是基本类型 int，所以它需要 4 个字节 - 恒定大小）。如果 p 增加，这并不意味着需要更多 space，而是存储了更大的数字。 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 个零）。

但实际上，在处理 "usual" 数据时，您不会期望有这么大的数量。由于仅超过 32 位寄存器（一个 int 数字），您需要有 2^32 个数据条目（1 个条目 = 4 个字节用于下一个引用，至少 4 个字节用于值 Object参考，object 大小本身 = 至少 8 字节），即 2^35 字节 = 32 GB。因此，当使用一个数字时，它通常被认为是一个常量 space 复杂度。这取决于任务和情况。

Answer 3

此算法唯一使用的 space 是 int p 的 space，无论输入如何，它都是常数，因此 space 复杂度为 O(1)。时间复杂度确实是O(N).

Java - Space 变量复杂度

Java - Space complexity with variable

space-complexity