algorithm - 试图理解这个算法的空间复杂度

Question

我在网上看到很多解释时间复杂度的文章，但没有找到任何好的解释空间复杂度的文章。我正在尝试解决以下面试问题

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the Ts digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE

Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.

Output: 2 -> 1 -> 9.That is, 912.

我的解决方案如下:

private Node addLists(Node head1, Node head2) {
    Node summationHead = null;
    Node summationIterator = null;
    int num1 = extractNumber(head1);
    int num2 = extractNumber(head2);
    int sum = num1 + num2;

    StringBuilder strValue = new StringBuilder();
    strValue.append(sum);
    String value = strValue.reverse().toString();
    char[] valueArray = value.toCharArray();
    for (char charValue : valueArray) {
        Node node = createNode(Character.getNumericValue(charValue));
        if (summationHead == null) {
            summationHead = node;
            summationIterator = summationHead;
        } else {
            summationIterator.next = node;
            summationIterator = node;
        }
    }
    return summationHead;
}

private Node createNode(int value) {
    Node node = new Node(value);
    node.element = value;
    node.next = null;
    return node;
}

private int extractNumber(Node head) {
    Node iterator = head;
    StringBuilder strNum = new StringBuilder();

    while (iterator != null) {
        int value = iterator.element;
        strNum.append(value);
        iterator = iterator.next;
    }
    String reversedString = strNum.reverse().toString();
    return Integer.parseInt(reversedString);
}

有人可以为此推断出空间复杂度吗？谢谢。

Answer 1

空间复杂度意味着“运行该算法所需的空间量如何随着输入变大而渐近变化”？

因此您有两个长度为 N 和 M 的列表。结果列表的长度将达到 max(N,M)，如果有进位，则可能为 +1。但 +1 是一个常数，我们不认为它是 Big-O 的一部分，因为 N 或 M 中较大的一个将占主导地位。

另请注意，此算法非常简单。没有需要大于线性空间的中间计算。

空间复杂度为max(N,M)。