algorithm - 如何将几个大 O 添加/合并为一个

Question

如果我有一个由（比方说）三个子算法组成的算法，它们都具有不同的 O() 特征，例如：

• 算法 A：O(n)
• 算法 B：O(log(n))
• 算法 C: O(n log(n))

我如何从理论上估计整个算法的 O()？即不计时或执行任何其他实际测量。

是否有众所周知的公式或程序？

Answer 1

是否有众所周知的公式或程序？

因为那是基本的数学，是的。但在你的情况下它更简单：因为所有这些都给出了一个上限，你可以简单地取所有界限中的最大值来获得总上限。

– 前提是所有这些算法都是链接的（而不是嵌套的）。如果算法是嵌套的，则需要乘以它们的上限（在最简单的情况下）。

为了说明，假设您有一个容器数据结构，其查找单个元素的成本为 O(log n )。您还有一个算法需要这样的查找，但它本身的运行时间为 O( n )，假设查找的成本恒定，并在输入上使用单个循环，每个循环的查找次数恒定。

现在，如果你想在这个算法中使用前面提到的容器数据结构，它的查找运行时显然取代了（假设的）恒定时间查找。所以我们有相同的循环，但是它的每次迭代现在都需要 O(log n ) 而不是恒定时间 O(1)，所以整个运行时间变成 O( n log n )。

Answer 2

“总”复杂度是所有​​子算法中最坏的情况。在您的示例中：O(n*log(n))

的定义O(f(n))是从某个数字（某个 n0）开始，有一个常数“Const”，其中对大小为 n 的输入的动作总数小于Const*f(n)。

因此，如果您有一组子算法，复杂度将始终小于所有 const 的 Sigma (Const1 + Const2 + ...) 乘以最差复杂度函数（例如，来自 "n"、"n*logn" 和“n^2”将是 n^2)。根据复杂性定义，它是该组中最差的复杂性。

例子：

1. 假设我们正在对数组进行排序(n*logn)
2. 找到键高于x的项目 (logn)

假设排序的 Const1 是 5（意味着我们可以在少于 5*n*logn 的动作中对 n 个项目的列表进行排序）并且 Const2 是 3（意味着我们可以在少于 3*logn 的动作中找到元素）。

在这种情况下，很明显两种算法的动作总数都小于(5+3)*n*logn动作，因此它O(n*logn)

Answer 3

O(n) 算法效率估计的假设之一是我们的实际运行时间接近理论值。因此，我们不应该过于纠结于轴试图找出小的差异。例如，如果我们对未排序的数据集进行简单的迭代搜索（平均而言，我们会在中间点找到值），那么 O(n) 算法可能会在 O(n/2) 时间内完成，但它仍然是一个 O(n) 算法。

如果你有一个函数必须在一个数据集上完成三个子进程才能退出，那么可以说，该数据集上运行时间最慢的子进程将是帐篷中最长的极点。在给出的具体示例中，函数 ('algorithm') 运行时间为 O(n)，如果是 O(n + n*log(n) + log(n))，我们不必担心；该总和与 O(n) 之间的差异最多是两倍。我们关心的是相对量级，即运行时间是log(n)，还是(n)，或者(n^2)，或者(n^3)，无穷无尽。我们关心的是 10 或 100 或 1000 的因数。

Answer 4

问题的复杂性由“n”趋于无穷大的条件决定。这个链接从根本上是为什么所有复杂度较低的 O(n) 数都被丢弃的原因；甚至 O(n) 格式也会丢弃其他多项式项，这些项会在不同的硬件上发生变化。合理地，如果您有函数的次数，您可以添加各种总次数。在时间相关的环境中，这可能是有意义的数据，例如处理大量数据，其中调用的函数被多次调用。这也可以提供解决方案的可扩展性和升级的性能峰值，比方说，服务器。这将是一个单机解决方案，并且系数也不会被丢弃。

所有机器在执行任何基于架构的功能以及编译器如何生成二进制代码时都会有不同的运行系数。这意味着，如果您正在为多个用户设计程序，并且他们在不同的计算机上，那么具体的计算不仅无关紧要，而且也不准确。

在计算不是无关紧要或不准确的情况下：

分离结构的诀窍是一个的时间函数不是所有其他的时间函数。

O(n) = x + y + z, 
x(n) = (t1) * (n^2)
y(n) = (t2) * (log n) 
z(n) = (t3) * (n log n) 

...

时间 (t1)、(t2) 和 (t3) 作为特定机器上的功能时间给出。