0

“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;           

    }

这对 Test、test、Hello 返回 false，对 SuperMan、SpiderMan 和 Sponge 返回 true，并且工作正常。

谢谢

4

4 回答 4

6

您的算法是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;
}
于 2013-08-20T18:32:00.050 回答
3

符号 O(N) 称为Big O Notation。它提供的是算法所需的（原始）操作量相对于其输入大小的上限。输入的大小通常表示为N。

如果原始操作的数量与输入大小无关，则算法的复杂度为 O(1)，即常数时间。

如果原始操作的数量随着 N 的增长而线性增长（即：当 N 翻倍时，操作的数量也会增加），那么时间复杂度是线性的，即 O(N)。

在您的示例中，对于普通读者来说，上限似乎是 O(N^2)：

for (each item in input)
  for (each item in input)
    // do something

当 N 翻倍时，运算量翻了两番。

但是，由于 ElementAt 的时间复杂度是线性的而不是恒定的，所以复杂度实际上是 O(N^3)。

于 2013-08-20T18:44:19.103 回答
1

不是 O(?) 的答案

但这接近 O(N)，因为 HashSet 应该接近 O(1)。
注意 HashSet.Count 是 O(1)。 

HashSet<char> chars = new HashSet<char>();
string password = "password";
Int32 count = 0;
char cUpper;
foreach (char c in password)
{
    count++;
    cUpper = char.ToUpper(c);
    if (!chars.Add(char.ToUpper(c))) 
    {
        System.Diagnostics.Debug.WriteLine("not uniue");
        break;
    }
}
if(count == chars.Count) System.Diagnostics.Debug.WriteLine("uniue");

+1 没有看到 Marcin 有这个答案减去 ToUpper
ToUpper 比 ToLower 更好用，但我忘记了为什么
String 有不区分大小写的比较但 char 没有

于 2013-08-20T18:49:51.847 回答
0

编辑：根据其他用户的建议，它是 O(n^3)，或者与三阶多项式成正比。这是因为ElementAt()循环遍历字符串。

这种复杂性的关键在于您的迭代。这种结构：

for (each item in this thing)
{
   for(each item in this thing)
   {
      if (iterate through this thing to check a condition)
   }
}

将有一个与三阶多项式成比例的增长阶。它没有像这样的其他例程那么糟糕，因为通过内部循环的内部迭代会随着您的增加而变小，但是您仍然在迭代字符串的每个元素，并为每个迭代遍历字符串。如果您的算法是 O(n^3)，您可能会对其进行重构。

没有ElementAt()调用，如果您有兴趣，它与选择排序的迭代方式非常相似。

于 2013-08-20T18:17:19.690 回答