如何计算此函数的时间复杂度,该函数检查字符串是否具有所有唯一字符？

Question

"Cracking the Coding Interview"一书,这个Stack Overflow问题讨论了一个确定字符串是否包含所有唯一字符的函数.本书使用位移的答案在问题链接中(请参见页面顶部的答案),我在此不再赘述.

Java答案有O(N)的复杂性,我无法理解O(N)实际意味着什么.我实际上想知道我刚刚写的这个实现的时间复杂度是多少.是O(N)？如何判断复杂性？

static void Main(string[] args)
    {
        string stringToCheck ;
        bool hasAllUniqueChars = false;
        stringToCheck = "Test";

        hasAllUniqueChars = CheckForUniqueChars(stringToCheck);

        Console.WriteLine("String is Unique {0}", hasAllUniqueChars);
        Console.Read();
    }

    private static bool CheckForUniqueChars(string stringToCheck)
    {
        for (int i = 0; i < stringToCheck.Length - 1; i++)
        {
            for (int j = i; j < stringToCheck.Length - 1; j++)
            {
                if (Char.ToUpper(stringToCheck.ElementAt(i)) == 
                    Char.ToUpper(stringToCheck.ElementAt(j+1)))
                {
                    return false;
                }
            }
        }
        return true;           

    }

对于SuperMan,SpiderMan和Sponge,它为Test,test,Hello和true返回false,并且工作正常.

谢谢

Answer 1

你的算法是O(n ^ 2),或者更准确 - 可能是O(n ^ 2).可能是,因为现在它是O(n ^ 3).

ElementAt()方法是O(n) on IEnumerable,因为它在两个嵌套循环中执行,整个方法是O(n ^ 3).

您可以通过将s转换为before循环并使用数组索引器而不是扩展方法来执行O(n ^ 2):stringchar[]ElementAt

private static bool CheckForUniqueChars(string stringToCheck)
{
    var chars = stringToCheck.ToCharArray();
    for (int i = 0; i < stringToCheck.Length - 1; i++)
    {
        for (int j = i; j < stringToCheck.Length - 1; j++)
        {
            if (Char.ToUpper(chars[i]) == Char.ToUpper(chars[j+1]))
            {
                return false;
            }
        }
    }
    return true;           
}

额外:另一种 O(n)方法(因为HashSet<T>查找是 O(1)):

private static bool CheckForUniqueChars(string stringToCheck)
{
    var characters = new HashSet<char>();

    foreach (var character in stringToCheck)
        if (!characters.Add(character))
            return false;

    return true;
}