如何正确理解算法的空间复杂性？

Question

我正在求解一个LeetCode问题来逆转K群中链表中的节点。

我已经写了以下的程序来逆转和它的工作良好。

package com.sample.testapp

class LinkedListPractice {
    class ListNode(val data: Int) {
        var next: ListNode? = null
    }
    companion object {
        @JvmStatic
        fun main(args: Array<String>) {

            var root: ListNode = ListNode(1)
            root.next = ListNode(2)
            root.next!!.next = ListNode(3)
            root.next!!.next?.next = ListNode(4)
            root.next!!.next?.next?.next = ListNode(5)
            println("Initial")
            prinLinkedList(root)

            var k = 2
            val answer = reverseKNodes(root, k)
            println()
            println("After reverse")
            prinLinkedList(answer)

        }

        fun prinLinkedList(root: ListNode?) {
            var current = root
            while (current != null) {
                print(current.data)
                current = current.next
                print("->")
            }
        }

        private fun reverseKNodes(root: ListNode?, k: Int): ListNode? {
            if (root == null) return null
            //reverse first k nodes and then call for next recursively until linkedlist ends
            var counter = 0
            var pre: ListNode? = null
            var next: ListNode? = null
            var current = root
            while (current != null && counter < k) {
                next = current?.next
                current?.next = pre
                pre = current
                current = next
                counter++
            }
            if (next != null) {
                root.next = reverseKNodes(next, k)
            }
            return pre
        }
    }
}

我只是困惑于计算这个程序的空间复杂度。

根据我的理解，我只是创建指向节点的指针并逆转它们，因此空间复杂性应该是常量的O(1)，但我怀疑ListNode pre和ListNode next是新的，然后将值分配给它们。

因此，当我们遍历所有K-群时，每次返回时都会创建一个新的预节点。那么，我应该把它的空间复杂性称为O(N)吗？

有谁能帮我解决这个疑问吗？

任何帮助都将不胜感激。

Answer 1

根据我的理解，我只是创建指向节点的指针并将其反转，因此空间复杂性应该是常数O(1)。

如果没有递归，它将是恒定的。但是每个递归执行上下文都有自己的一组变量--参数root和k以及其他局部变量counter、pre、next和current。当发生ceil(n/k)递归调用时，这六个变量中有同样多的变量(每个变量占用一定的内存)，空间复杂度为O(n/k)。

我怀疑ListNode pre和ListNode next是新的，然后将值分配给它们。

它们是局部变量。这里使用" new“一词有点含糊不清，因为我们不应该考虑节点的新实例。它们所使用的唯一内存是用于存储对象引用(指针)。

因此，当我们遍历所有K-群时，每次返回时都会创建一个新的pre节点。

没有创建新的节点(代码中没有Node()构造函数调用)。返回的引用始终是现有的引用，用于覆盖next属性中的旧引用。

那么，我应该把它的空间复杂度称为O(N)吗？

是O(n/k)

若要使其成为O(1)，请将递归转换为循环。这需要更多的变量：

    private fun reverseKNodes(root: ListNode?, k: Int): ListNode? {
        var counter = 0
        var pre: ListNode? = null
        var next: ListNode? = null
        var newRoot: ListNode? = null
        var tail: ListNode? = null
        var prevTail: ListNode? = null
        var current = root
        while (current != null) {
            tail = current
            counter = 0
            pre = null
            next = null
            while (current != null && counter < k) {
                next = current?.next
                current?.next = pre
                pre = current
                current = next
                counter++
            }
            if (newRoot == null) {
                newRoot = pre
            } else {
                prevTail?.next = pre
            }
            prevTail = tail
        }
        return newRoot
    }

请注意，这是而不是-- LeetCode挑战的解决方案，因为该代码挑战规定：

如果节点的数量不是k的倍数，那么剩下的节点最终应该保持原样。

这不是您的代码所做的。因此，您需要添加额外的逻辑来向前看，并在执行块的实际反转之前检查前面仍然有k个节点：

    fun reverseKGroup(root: ListNode?, k: Int): ListNode? {
        var counter = 0
        var pre: ListNode? = null
        var next: ListNode? = null
        var newRoot: ListNode? = null
        var tail: ListNode? = null
        var prevTail: ListNode? = null
        var current = root
        var node: ListNode? = null
        while (current != null) {
            tail = current
            counter = 0
            pre = null
            next = null
            node = current
            for (i in 1..k) {
                if (node == null) {
                    if (prevTail != null) {
                        prevTail?.next = current
                    }
                    return newRoot ?: root
                }
                node = node?.next
            }
            while (current != null && counter < k) {
                next = current?.next
                current?.next = pre
                pre = current
                current = next
                counter++
            }
            if (newRoot == null) {
                newRoot = pre
            } else {
                prevTail?.next = pre
            }
            prevTail = tail
        }
        return newRoot
    }