这个二元加法解的 space 复杂度是多少？

Question

的面试问题

问题：写一个函数，给定两个二进制数作为字符串returns它们的二进制数之和

这是我在Java中的解决方案（已测试，有效！！！）

private static String sum(String bin1, String bin2)
{
    int dec1 = binToDec(bin1);
    int dec2 = binToDec(bin2);
    int sumTo = dec1 + dec2;
    StringBuilder bin = new StringBuilder();
    do {
        bin.append(sumTo%2);
        sumTo = sumTo/2;
    }while(sumTo > 0);

    return bin.reverse().toString();
}
private static int binToDec(String bin) 
{
    int result = 0;
    int len = bin.length();
    for(int rep = len-1; rep >= 0; rep--) {
        int multiplyBy = bin.charAt(rep) == '1' ? 1 : 0;
        result += multiplyBy * Math.pow(2, len-1-rep);
    }
    return result;
}

我正在尝试分析总和的时间和 space 复杂性。我知道我的算法的时间复杂度只是 O(logn) 因为二进制转换。

像往常一样，我遇到了 space 复杂度问题。我知道 space 复杂度只取决于我从堆中分配的内存，在本例中是表示二进制和结果的字符串

我知道字符串连接是一项昂贵的操作，因为它需要复制 1 个字符，然后是 2 个字符，最后是 logn 个字符。我知道传统的字符串连接在 O(n²) space 中运行。这里也会一样吗？

我试着自己算了算

1 + 2 + 3 +.... logn-1 + logn <BR>
logn + logn-1 + ....1<BR>
 logn(logn + 1)/2

得到最终结果^{logn(logn + 1)}⁄₂ 这将是 O((logn)²)。这个算法的 space 复杂度是正确的吗？或者只是 O(n²) 因为这两个函数属于同一个家族？

Answer 1

重新审视这个问题后，我应该对变量的使用更加清楚了。

我算法的时间复杂度是O(log₂m + n₁ + n₂) Big O Summation 其中 m 是二进制数之和的十进制表示。 n₁和n₂是位数, 或分别为 bin1 和 bin2 的长度。

对于，您必须考虑算法分配的所有内存 - 来自堆栈和堆。

在分析我从中使用的 space 的数量时，我注意到我没有进行递归调用 space 将是 O(1)。同样，在分析我从堆中使用的 space 的数量时，它也将是 O(1) 因为无论输入如何，我总是分配相同数量的space（3 个整数），不使用数据结构。

因此，我的解决方案的 space 复杂度为 O(1)

这个二元加法解的 space 复杂度是多少？

What is the space complexity of this binary addition solution?

java

string

algorithm

time-complexity

space-complexity