黑马程序员技术交流社区

标题: 【上海校区】Python复杂度O(1)实现N个整数之和 [打印本页]

---

作者: 梁强    时间: 2018-9-22 10:55
标题: 【上海校区】Python复杂度O(1)实现N个整数之和

学 Python 仅仅只学 Python 语法和 API 是远远不够的，掌握算法和数据结构这种永远都不会过时的核心技能才是决定一个程序员职业发展的关键因素。算法和数据结构对专业程序员来说重要性不言而喻，同样一个问题，不同算法效率可谓千差万别。在问题规模很小的时候你可能感知不到，但是一旦数据上升到TB级别时，两者的差距就像西瓜和芝麻的差别了。

举个简单例子：我们要计算前n个整数之和，你最先想到的算法可能是迭代：

[Python] 纯文本查看 复制代码

def sumOfN(n):

    theSum = 0

    for i in range(1,n+1):

        theSum = theSum + i



    return theSum



print(sumOfN(10))

代码非常直观，初学者都能读懂，就是从1累加到n，得到最后的结果。这种算法的效率随着n的增加而变化，时间复杂度是O(n)，线性时间，大O表示法指出了最糟糕情况下的运行时间。想象一下，这个数足够大的时候，所耗费的时间将是无法估量的，当然，还有很多比线性时间更糟糕的算法

当然，最后还有一种最理想的算法，就是常数级别的，O(1) 常数级复杂度。也就是说程序运行的时间与需要处理的数据大小无关。

如果利用数学方程而不是迭代来计算前n个整数的和，他的复杂度就是 O(1)

[Python] 纯文本查看 复制代码

def sumOfN3(n):

   return (n*(n+1))/2



print(sumOfN3(10))

Google这样大数据公司，数据都是以TB为单位的数据量，索引的网页数量超过1万亿的情况下，没有牛逼的算法，难以撑起一个巨无霸公司。很多人觉得学算法没什么用，因为工作上就是调API，写写业务逻辑，学这些干什么？如果这么想，那你永远都是在写业务逻辑代码，写到35岁转行。

---

作者: Yin灬Yan    时间: 2018-9-25 15:16
关于复杂度 我的认知基本是0  迷糊的不行

---

作者: 不二晨    时间: 2018-10-10 11:47
奈斯

---

作者: 魔都黑马少年梦    时间: 2018-11-1 16:38

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2