二进制搜索复杂性 [英] Complexity of Binary Search

问题描述

我看伯克利统一的在线讲座和贴在下面。

问题：假设你有一个CD的集合已经排序。你想找到CD的列表其标题以最好。

解决方案：我们将使用二进制搜索找到最佳的第一种情况，然后我们打印，直到瓷砖不再是最佳

其他问题：查找该算法的复杂度

上限的：绑定二进制搜索上是O（log n）的，所以一旦我们发现它，然后我们打印让说ķ称号。所以它是O（LOGN + K）

下限的：二进制搜索下限是欧米茄（1）假设我们是幸运的录像标题是中级职称。在这种情况下，它是欧米加（k）的

这是我分析的方式。

但在讲座中，讲师用最好的情况和最坏的情况。 我有两个问题吧：

1. 为什么需要用最好的和最坏的情况下，都没有大O和欧米茄认为​​是最好的和最坏的情况下，该算法可以执行？

2. 他的分析是                 最差情况：西塔（LOGN + K）
                   最佳情况：西塔（K）

   如果我用最坏情况下的概念，指的是数据并没有什么做与算法，然后是的，他的分析是正确的。 这是因为，假设最坏的情况下（到底还是没有找到CD标题），那么大O和欧米茄既为log N它就在那里THETA（日志N + K）。

   假设你不这样做最好情况和最坏情况，那你怎么分析的算法？是我的分析对吗？

解决方案

  

为什么需要用最好的和最坏的情况下，都没有大O和欧米茄视为算法可以执行的最好和最坏的情况？

没有，在Ο和Ω符号也只能描述一个函数来描述算法的实际行为的渐近行为的界限。这里是一个很好

• Ω介绍了下限：F（ N 的）∈Ω（克（的 N 的））表示f的渐近性（ N 的）是不小于克（ N 的）· K 的一些积极的 K 的，所以F（ N 的）是总是至少不亚于克（ N 的）· K 的。
• Ο描述上限：F（ N 的）∈Ο（克（的 N 的））表示f的渐近性（ N 的）是不超过克（ N 的）· K 的一些积极的 K 的，所以F（ N 的）是总是最多高达克（ N 的）· K 的。

这些2可以同时在最好的情况下，最坏情况下的二进制搜索被应用

• 在最好的情况：你看第一个元素是你正在寻找一个
  • Ω（1）：你需要的至少的一个查找
  • Ο（1）：你需要的最多的一个查找
• 在最糟糕的情况：元素不是present
  • Ω（日志的 N 的）：你需要的至少的日志的 N 的步骤，直到你可以说，你正在寻找的元素不是present
  • Ο（日志的 N 的）：你需要的最多的日志的 N 的步骤，直到你可以说，你正在寻找的元素不是present

您看到的，Ω和Ο值相同。在这种情况下，你可以说的紧约束的最好的情况是Θ（1），最坏的情况是Θ（日志的 N 的）。

但往往我们只是想知道上限或紧约束的下界已经没有太大的实用信息。

  

假设你不这样做最好情况和最坏情况，那你怎么分析的算法？是我的分析对吗？

是的，你的分析似乎是正确的。

I am watching the Berkley Uni online lecture and stuck on the below.

Problem: Assume you have a collection of CD that is already sorted. You want to find the list of CD with whose title starts with "Best Of."

Solution: We will use binary search to find the first case of "Best Of" and then we print until the tile is no longer "Best Of"

Additional question: Find the complexity of this Algorithm.

Upper Bound: Binary Search Upper Bound is O(log n), so once we have found it then we print let say k title. so it is O(logn + k)

Lower Bound: Binary Search lower Bound is Omega(1) assuming we are lucky and the record title is the middle title. In this case it is Omega(k)

This is the way I analyzed it.

But in the lecture, the lecturer used best case and worst case. I have two questions about it:

1. Why need to use best case and worst case, aren't big-O and Omega considered as the best and worst cases the algorithm can perform?

2. His analysis was Worst Case : Theta(logn + k)
   Best Case : Theta (k)

   If I use the concept of Worst Case as referring to the data and having nothing to do with algorithm then yep, his analysis is right. This is because assuming the worst case (CD title in the end or not found) then the Big O and Omega is both log n there it is theta(log n +k).

   Assuming you do not do "best case" and "worst case", then how do you analyze the algorithm? Is my analysis right?

解决方案

Why need to use best case and worst case, aren't big-O and Omega considered as the best and worst cases the algorithm can perform?

No, the Ο and Ω notations do only describe the bounds of a function that describes the asymptotic behavior of the actual behavior of the algorithm. Here’s a good

• Ω describes the lower bound: f(n) ∈ Ω(g(n)) means the asymptotic behavior of f(n) is not less than g(n)·k for some positive k, so f(n) is always at least as much as g(n)·k.
• Ο describes the upper bound: f(n) ∈ Ο(g(n)) means the asymptotic behavior of f(n) is not more than g(n)·k for some positive k, so f(n) is always at most as much as g(n)·k.

These two can be applied on both the best case and the worst case for binary search:

• best case: first element you look at is the one you are looking for
  • Ω(1): you need at least one lookup
  • Ο(1): you need at most one lookup
• worst case: element is not present
  • Ω(log n): you need at least log n steps until you can say that the element you are looking for is not present
  • Ο(log n): you need at most log n steps until you can say that the element you are looking for is not present

You see, the Ω and Ο values are identical. In that case you can say the tight bound for the best case is Θ(1) and for the worst case is Θ(log n).

But often we do only want to know the upper bound or tight bound as the lower bound has not much practical information.

Assuming you do not do "best case" and "worst case", then how do you analyze the algorithm? Is my analysis right?

Yes, your analysis seems correct.

这篇关于二进制搜索复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！