了解Big-O符号
了解Big-O符号
提问于 2014-08-26 05:19:26
我正在读西蒙·哈里斯和詹姆斯·罗斯写的一本书“算法入门”。
在前面的页面中，有一个关于理解Big-O表示法的部分。我读了这一节，可能重读了这一节十几次。我仍然不能理解几件事。我很感谢任何帮助我摆脱困惑的人。
作者/作者说：“运算的精确数量实际上并不那么重要。算法的复杂性通常是根据执行函数所需的运算数量的数量级来定义的，用大写字母O表示顺序，后面跟着一个表达式，表示相对于字母N表示的问题大小的一些增长。”
这真的让我头疼，不幸的是，这段话后面的一切对我来说都没有意义，因为这段话应该是为下一段阅读奠定基础的。
这本书没有定义“数量级”。我用谷歌搜索了一下，结果告诉我，数量级定义为10的幂。但这到底是什么意思呢？你是否将操作的数量定义为10的幂，这等于复杂度？另外，什么是“问题的大小”？问题的大小就是操作的数量吗？或者问题的大小是“执行一个功能所需的操作数量的数量级”。
任何实际的例子和对此的适当解释都会很有帮助。
谢谢!
回答 1
Stack Overflow用户
发布于 2014-08-26 05:36:12
保持简单！
只需将Big-O视为表示算法节奏性能的一种方式。性能将取决于算法处理的元素数= n。
一个例子，当你必须做一个和的时候。第一次添加需要一条语句，第二次添加需要一条语句，依此类推……因此，性能将与元素数量= O(n)呈线性关系。
想象一下排序算法algorythm，它非常聪明，对于句柄的每个元素，它自动缩短下一个元素的排序。这将是元素数量= O(log(n))的对数。
或者一个带有参数的复杂公式，每多一个参数，执行时间就会成倍增加。这将是指数= O(10^n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25494524
复制相关文章
相似问题
腾讯云开发者
