Big O 异常运行时

Question

我有一个自定义 Dictionary<T>，它的后备集合 KeyedCollection。在尝试优化我在探查器中运行时看到的性能问题时，我注意到 IndexOf(T key) 是我的问题领域之一。目前代码实现如下：

public int IndexOf(TKey key)
{
     if (keyedCollection.Contains(key))
     {
         return keyedCollection.IndexOf(keyedCollection[key]);
     }
     else
     {
         return -1;
     }
}

我知道 Contains(T key) 和 IndexOf(T key) 都具有 O(n) 的大 O 运行时，并且已在 MSDN 站点上确认了这一点。 (https://msdn.microsoft.com/en-us/library/ms132438(v=vs.110).aspx)
我认为优化这段代码的一个好方法是去掉其中一个 O(n) 操作，所以我将代码更改为：

public int IndexOf(TKey key)
{
     try
     {
         return keyedCollection.IndexOf(keyedCollection[key]);
     }
     catch (KeyNotFoundException)
     {
         return -1;
     }
}

当我比较两者之间超过 500,000 次操作的运行时间时，带有 Contains(T key) 的代码执行 try-catch 场景的时间接近 2 倍。

我的问题是，使用会大大降低性能的 try-catch 块是否会产生大量开销？

Answer 1

这里抛出异常的时间复杂度为 O(1)，因为抛出和捕获异常的成本与集合的大小无关；这将是固定成本。固定成本可能很高，但不会增长。

Big O 异常运行时

Big O Runtime of Exceptions

c#

big-o

keyedcollection