线性时间算法之和是线性时间吗？
线性时间算法之和是线性时间吗？
提问于 2012-09-18 14:31:01
如果这个问题是“愚蠢的”，请原谅。我对算法的时间复杂度很陌生。
我知道，如果我有n个数字，我想要和它们，它采取"n步“，这意味着算法是O(n)或线性时间。即，所采取的步骤数与输入数，n成线性关系。
如果我写了一个新的算法，一个接一个地进行5次求和，我知道它是O(5n) = O(n)时间，仍然是线性的(根据维基百科)。
问题
如果我有10个不同的O(n)时间算法(和，线性时间排序等)。我在n个输入上一个接一个地运行。
这是否意味着总体上这是在O(10n) = O(n)线性时间内运行的？
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-09-18 14:32:43
对任意常数 k，= O(n)，O(kn)
如果您开始增加您的问题，并决定您的10个线性操作实际上是基于k个线性运算，例如k是一个用户输入数组的长度，那么从这个大的--哦，掉掉这个信息是不正确的。
Stack Overflow用户
发布于 2012-09-18 17:26:10
是的，O(10n) = O(n)。另外，O(C*n) = O(n)，其中C是常数。在这种情况下，C是10，如果C等于n，它可能是O(n^2)，但这不是真的。因为C是常数，所以它不随n而变化。
另外，请注意，在复杂性之和中，最高阶或最复杂的阶被认为是总体复杂性。在这种情况下，它是O(n) + O(n) .+ O(n)十次。因此，它是O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12479114
复制相关文章
相似问题
腾讯云开发者
