string - 为什么这个算法的时间复杂度是指数级的？

Question

在一次面试中，有人问我以下算法的时间复杂度:

static bool SetContainsString(string searchString, HashSet<string> setOfStrings)
{
    for (int i = 0; i < searchString.Length; i++)
    {
        var segment = searchString.Substring(0, i + 1);

        if (setOfStrings.Contains(segment))
        {
            var remainingSegment = searchString.Substring(segment.Length);

            if (remainingSegment == "") return true;
            return SetContainsString(remainingSegment, setOfStrings);
        }
    }

    return false;
}

我回答“线性”是因为在我看来它只循环遍历 searchString 的长度。是的，它是递归的，但是递归调用只针对字符串中还没有迭代的部分，所以最终的迭代次数就是字符串的长度。

我的面试官告诉我，最坏情况下的时间复杂度是指数级的。

谁能帮我澄清一下？如果我错了，我需要明白为什么。

Answer 1

我认为您的面试官在这里是不正确的。以下是我如何论证为什么时间复杂度不是指数级的:

• 对函数的每次调用都会进行零次或一次递归调用。
• 每次递归调用都会将字符串的长度至少减少一个。

这限制了 O(n) 的递归调用总数，其中 n 是输入字符串的长度。每个单独的递归调用执行多项式的工作量，因此完成的总工作量是一些多项式。

我认为您的面试官在这里感到困惑的原因是上面给出的代码——我认为它应该检查一个字符串是否可以分解为一个或多个单词——在所有情况下都不能正常工作。特别要注意的是，递归总是乐观地捕获它发现的第一个单词前缀，并假设它捕获的是将单词分开的正确方法。但是想象一下你有一个像“applesauce”这样的词。如果你去掉“a”并尝试递归地形成“pplesauce”，你会错误地报告这个词不是一个复合词，因为没有办法分解“pplesauce”。要解决此问题，您需要将递归调用更改为如下所示:

if (SetContainsString(...)) return true;

这样，如果您选择了错误的拆分，您将继续检查您可以进行的其他可能的拆分。代码的这种变体确实在最坏的情况下会花费指数时间，因为它可能会多次重新访问相同的子字符串，我认为这就是面试官错误地认为你在做的事情。