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

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是输入字符串的长度.每个单独的递归调用都会执行多项式的工作量,因此完成的总工作量是一些多项式.

我认为你的面试官在这里感到困惑的原因是上面给出的代码 - 我认为应该检查字符串是否可以分解为一个或多个单词 - 在所有情况下都不能正常工作.特别要注意的是,递归的工作原理是始终乐观地抓住它找到的第一个前缀,这是一个单词,并假设它抓住的是将单词分开的正确方法.但想象你有一个像"苹果酱"这样的词.如果你拉掉"a"并尝试递归形成"pplesauce",你就会错误地报告这个词不是复合词,因为它无法分解"pplesauce".要解决此问题,您需要将递归调用更改为以下内容:

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

这样,如果您选择了错误的拆分,您将继续检查您可以进行的其他可能的拆分.代码中的那个变体确实在最坏的情况下需要指数时间,因为它可能会多次重新访问相同的子串,并且我认为那是面试官错误地认为你正在做的事情.