algorithm - 算法的最佳情况

Question

例如，如果我对某个数据结构有递归算法

Algo(Tree T)
    if T == null
        return false
    ...

该算法的最佳情况是当树为空时吗？时间复杂度是O(1)？

标签： algorithmtime-complexity

Answer 1

通常在谈论算法的最佳情况时间复杂度时，我们会说它是 size 输入的最佳情况n。

例如，考虑一个排序算法。如果排序算法不做任何更改并且只在输入列表已经排序的情况下迭代一次，那么我们会说在最好的情况下，算法是O(n)。当然，输入列表可能是空的，但这与操作数量随着增加而增长的方式无关n。