改善"增加数字表示的数字"的时间复杂性

Question

问题 给定一个非负数表示为数字数组,

将数字加1(增加数字所代表的数字).

存储数字使得最高有效数字位于列表的开头.

例:

如果向量有[1,2,3]

返回的向量应为[1,2,4]

因为123 + 1 = 124.

我的守则

def plusOne(A):
    num = 0

    for digit in A:
        num = num*10 + digit

    retnum = num + 1

    retA = []

    while retnum > 0:
        retA.append(retnum % 10)
        retnum /= 10

    return retA[::-1]

好吧,我得到了正确答案.但是,我对代码的时间复杂性并不满意.建议改进此代码.

Answer 1

你的方法的复杂性是O(n),在最坏的情况下,你无法在大复杂性方面做得更好.

然而,改变大的复杂性并不是唯一重要的事情.Big-o表示法没有考虑乘法和加法常数,这并不意味着这些常数不会影响算法的性能.例如,在您的代码中,您执行了2 O(n)个循环.在第一个循环中,您执行一些算术运算,而在您使用的第二个循环中append,已经分摊了最坏情况O(1),但是(引用文档):

[...]依赖于"摊销最坏情况"的"摊销"部分.根据容器的历史,个别动作可能需要很长时间.

您可以使用(我认为)较小的常量执行相同的操作.例如:

i = len(A) - 1

while i >= 0 and A[i]==9:
  A[i]=0
  i=i-1

if i >= 0:
  A[i] = A[i]+1
else:
  A.insert(0,1)

第一个循环在最坏的情况下需要O(n)时间(全部为9).然而,在平均情况下,循环小于O(n).当我们在最坏的情况下退出循环时,我们需要在列表的开头插入一个元素,该元素具有非摊销的 O(n)复杂度.

在一般情况下,这种方法应该更快,但它不会改变最坏情况下的O(n)复杂性.