我有一个看起来像这样的算法：
if condition
O(1) algorithm
else
O(n)
现在，当条件始终为 false 时，最坏情况的运行时是 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)。
这就是我的看法，我可能错了:)
Big-O 分析用于描述最坏情况的复杂性，因此该算法的整体 big-O 为 O(n(。
你的 if 条件只是一个优化——你可以简单地在你的分析中声明你期望优化在x %的时间内有效......
首先，我认为"平均复杂度是O(n("是一个正确的说法，因为平均复杂度不应该比最坏情况的复杂性最差。
如果你想找到一个更好的数字，你需要从平均案例复杂度的定义中定义平均值的含义。它通常与投入的分布有关。一旦你发现条件"平均"为假的概率，你就可以找出复杂性。 我建议你看看这个例子。 https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array
如果您告诉我们有关条件/算法的更多信息，也会很有帮助。
事实上，我想也许你想要的不是理论上的复杂性。我猜你想要一个带有真实数据的基准/时间分析。
设 x = 条件为假的次数。
如果 x 可以由常数限定，则算法为 O(1(。否则为 O(n(。