我有一个看起来像这样的算法:
if condition
O(1) algorithm
else
O(n)
现在，当条件始终为假时，最坏情况的运行时间是 O(n)。然而，在实践中，该条件通常是正确的。如何分析该算法的平均运行时复杂度？或者它根本不适用？摊余分析是否更合适？
最佳答案
该算法是渐近O(n)的，因为随着n的增长，复杂性也会线性增长。然而，根据 O(n) 情况的概率，系数会相当低。
它不可能是O(1)，因为这意味着更改n不会影响预期的算法时间 - 而且这不是真的。
更新:如果 O(n) 情况仅在很小一部分时间内发生怎么办？
如果false值是预期，即使很少，那么我仍然会说它的O(n)。
如果是某种意外的异常情况，那么可能可以称为O(1)。
例如，如果 0.0001% 的值是 false，则其 O(n)，因为增加 n 仍会增加算法时间.
如果它总是true除非存在问题/特殊的“坏”输入情况/异常/错误，并且在好的情况下你永远不会得到false，然后是 O(1)。
这就是我的看法，我可能是错的:)
关于algorithm - if 语句的平均运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45049387/