尝试理解连接字符串输出的空间复杂度

Question

我在编码面试中遇到了这个问题：

# AAABB should return A3B2

这是一道经典的算法面试题。我说我可以在O(n)时间和O(1)空间上解决这个问题。

def compress(s):

    output = ''
    count = 1

    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            count+=1
        else:
            output = output + s[i] + str(count)
            count=1

    output = output +s[i+1] + str(count)
    return output

compress('AAABB') #returns A3B2

我理解O(n)空间意味着它随着输入的大小成比例地增长。所以我想O(n)空间看起来会是这样的 [(A,3),(B,2)]。

我的印象A3B2是在O(1)太空中，因为它没有被分成多个字符串。

我现在意识到，n == len(s)我的输出与我的输入大小不成比例（更少）地增长，所以说空间是正确的吗O(log n)？

Answer 1

必须计算您存储的输出字符串的长度。在最坏的情况下（没有连续的字符匹配），它\xe2\x80\x99实际上是输入长度的两倍。很明显，一般来说，\xe2\x80\x99s O ( n )：如果你知道长输入总是包含很长的运行，那么它只会渐近更好。（最好的情况是所有字符都相同，并且单个数字的长度为O (log  n )。）

\n\n

也就是说，有时将您的输出视为流（如print）很有用，然后您的空间复杂度（对于count当前输入字符）是恒定的。当然，即使这样，它在技术上也是对数的，因为需要存储的位数count是，但在实际分析中，\xe2\x80\x99 经常被忽略。

\n