1

方法是：

List<Book> books = new List<Book>();

public List<Book> Shoot()
{
   foreach(var b in books)
   {
       bool find = true;
       foreach(var otherb in books)
       {
           if(otherb != b && otherb.Author == b.Author)
           {
               find = false;
           }
       }

       if(find)
       {
           yield return b;
       } 
   }
}

通常，时间复杂度为 O(books.Count^2)，但在外循环中有一个 if(find) 语句，它可能会改变循环次数。

所以我的问题是：

  1. 这种方法的时间复杂度是多少？
  2. 你是怎么计算的？

我在网上等你的答复。

先感谢您。

4

2 回答 2

3

您将在外循环（n）中浏览每本书，对于每本外书，您将在内循环（n 次）中相互浏览，因此时间复杂度为 O（n^2）。

yield return 不会改变算法的复杂性，它会创建一个迭代器模式，但是如果你从调用函数遍历整个列表，你会经历算法中的所有迭代。

C# 中使用的 yield 关键字是什么？

为了优化算法，正如 btilly 提到的，您可以对集合进行两次遍历，在第一次遍历时，您将每个作者的书籍数量存储在哈希表中，在第二次遍历时，您检查作者是否有不止一本书使用哈希表（假设查找的时间是恒定的），如果确实如此，则产生这本书：

public List<Book> Shoot()
{
    var authors = new Dictionary<string, int>();
    foreach(var b in books) 
    {
        if(authors.ContainsKey(b.Author))
            authors[b.Author] ++;
        else
            authors.Add(b.Author, 1);
    }

    foreach(var b in books) 
    {
        if(authors[b.Author] == 1)
            yield return b;
    }
}

这样你就有了 O(n) 的线性时间复杂度，注意在这种情况下你需要 O(n) 额外的空间。

于 2012-06-29T00:26:43.853 回答
1

您的单产最差表现是O(n * n). 你最好的情况是O(n). 如果假设作者是随机排序的，固定部分只写一本书，那么收益率之间的平均情况是O(n)因为到达m外循环迭代的概率随着m增加而呈指数下降。（在此处插入标准几何级数参数。）

通常（但并非总是如此！）人们对平均情况最感兴趣。

顺便说一句，处理这个问题的标准方法是预先创建一个包含所有作者的字典，以及他们写了多少本书。那需要时间O(n)。然后您的收益将只搜索该字典的键，以查找只有 1 个条目的下一个。随后收益率的平均时间将是O(1)，最坏情况下O(n)，所有收益率的摊销平均时间（假设固定比例只写一本书）将是O(1)每个收益率。与当前O(n)按产量执行的实现相反。

于 2012-06-29T00:38:15.067 回答