如果我有一个算法，由三个子算法组成，每个子算法的O()特征都不同，例如：
- 算法A：O(n) - 算法B：O(log(n)) - 算法C：O(n log(n))
如何理论上估计整个算法的O()？即不进行任何实际测量或操作。
是否有一个公式或流程是众所周知的？
- 算法A：O(n) - 算法B：O(log(n)) - 算法C：O(n log(n))
如何理论上估计整个算法的O()？即不进行任何实际测量或操作。
是否有一个公式或流程是众所周知的？
如何将几个 Big O 合并成一个
4
- sharkin
2
把表现最差的部分作为整体表现是否有意义？ - Rich Bradshaw
只是一个警告，确保在每个算法中，“n”指的是同一件事情，否则你会遇到麻烦。 - Tim
4个回答
9
有没有一个众所周知的公式或过程呢？
由于这是基本数学，答案是肯定的。但在您的情况下，更简单：由于所有这些都给出了上限，您可以简单地取所有上限的最大值来获得总的上限。
- 前提是所有这些算法都是链接的（而不是嵌套的）。如果算法是嵌套的，则需要将它们的上限相乘（在最简单的情况下）。
举个例子，假设您有一个容器数据结构，查找单个元素的成本为O(log n)。您还有一种需要这样的查找的算法，但其自身的运行时间为O(n)，假设查找的成本恒定，并使用对输入的单个循环，每次循环有恒定数量的查找。
现在，如果您想在此算法中使用先前提到的容器数据结构，则其查找运行时显然会替换（假定）常量时间查找。因此，我们有相同的循环，但是它的每个迭代现在需要O(log n)，而不是常量时间O(1)，因此总运行时间变为O(n log n)。
由于这是基本数学，答案是肯定的。但在您的情况下，更简单：由于所有这些都给出了上限，您可以简单地取所有上限的最大值来获得总的上限。
- 前提是所有这些算法都是链接的（而不是嵌套的）。如果算法是嵌套的，则需要将它们的上限相乘（在最简单的情况下）。
举个例子，假设您有一个容器数据结构，查找单个元素的成本为O(log n)。您还有一种需要这样的查找的算法，但其自身的运行时间为O(n)，假设查找的成本恒定，并使用对输入的单个循环，每次循环有恒定数量的查找。
现在，如果您想在此算法中使用先前提到的容器数据结构，则其查找运行时显然会替换（假定）常量时间查找。因此，我们有相同的循环，但是它的每个迭代现在需要O(log n)，而不是常量时间O(1)，因此总运行时间变为O(n log n)。
- Konrad Rudolph
2
一个例子，如何将O(n)乘以O(n log(n))? - sharkin
1@R.A.：通过将指定边界的函数相乘，即结果为O(n^2 log n)。 - Konrad Rudolph
4
“总体”复杂度是所有子算法的最坏情况。在您的示例中：
因此，如果您有一组子算法，则复杂度始终会小于所有常数（Const1 + Const2 + ...）乘以最坏复杂度函数（例如，“n”，“n*logn”和“n^2”将是n^2）。按照复杂性定义，它是该组中的最坏复杂度。
例如：
在这种情况下，很明显，两个算法的总操作数都小于
O(n*log(n))。
O(f(n))的定义是从某个数字（某个n0）开始，存在一个常数“Const”，其中输入大小为n的操作总数小于Const*f(n)。因此，如果您有一组子算法，则复杂度始终会小于所有常数（Const1 + Const2 + ...）乘以最坏复杂度函数（例如，“n”，“n*logn”和“n^2”将是n^2）。按照复杂性定义，它是该组中的最坏复杂度。
例如：
- 假设我们正在对数组进行排序
(n*logn) - 查找关键字高于x
(logn)的项
在这种情况下，很明显，两个算法的总操作数都小于
(5+3)*n*logn操作，因此它是O(n*logn)。- Elisha
2
这将取决于算法是否相对地运行相同的次数，或者是否存在乘法效应，如果存在乘法效应，则必须将它们相乘。 - Joe
@Joe，你说得对，这个分析与序列运行相关，而不是嵌套运行，希望这回答了你的问题 :)
只要算法运行的次数是恒定的且不依赖于n，即使某些算法运行多次，结果仍然相同。 - Elisha
0
问题的复杂度是由条件“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) 作为特定机器上函数的时间给出。
- Accountingman
0
O(n) 算法效率估计的一个假设是我们的实际运行时间接近理论值。因此，我们不应该过于纠结于小的差异。例如，如果我们对未排序的数据集进行简单的迭代搜索（平均来说，在一半的位置上我们就能找到值），那么 O(n) 算法可能会在 O(n/2) 的时间内完成，但它仍然是一个 O(n) 算法。
如果你有一个需要在数据集上完成三个子进程才能退出的函数，则最慢的子进程在该数据集上的运行时间将成为帐篷中最长的杆子。在给定的具体示例中，函数（“算法”）的运行时间为 O(n)，我们不必担心它是否是 O(n + n*log(n) + log(n))；这个总和与 O(n) 之间的差异最多只有两倍。我们关心的是相对大小，即运行时间是否为 log(n)、(n) 或 (n^2) 或 (n^3) 等。我们关心的是 10、100 或 1000 倍数。
- John Clifford
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接