python – 提高时间复杂度“增加数字表示的数字”

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 提高时间复杂度“增加数字表示的数字”，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1266字，纯文字阅读大概需要2分钟。

内容图文

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

将数字加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]

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

解决方法:

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

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

[…] rely on the “Amortized” part of “Amortized Worst Case”. Individual actions may take surprisingly long, depending on the history of the container.

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

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)复杂性.

内容总结

以上是互联网集市为您收集整理的python – 提高时间复杂度“增加数字表示的数字”全部内容，希望文章能够帮你解决python – 提高时间复杂度“增加数字表示的数字”所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端