大O或大Θ？ [英] Big O or Big Θ?

问题描述

我知道大O和大Θ的差异，但我能找到的少数情况下，我真的需要使用大O或大Ω，而不是大Θ。

I know the difference of Big O and Big Θ, but I can find few cases where I really need to use Big O or Big Ω instead of Big Θ.

当的算法并且也运行时间复杂性的情况下（平均值，最差和最好）给出，我们可以测量算法的运行时间，并说明其作为Θ。 （请注意算法是指一个明确的，一步一个问题一步解决办法，纠正我，如果我错了）

When the algorithm and also the case of running time complexity (average, worst and best) are given, we can measure the running time of the algorithm and state it as Θ. (Please notice algorithm means a clear and step by step solution for a problem, correct me if I am wrong)

在一方面只是说的算法的运行时间不指定的情况下的复杂性是不明确的。在另一方面，如果它指的是这些案件之一，那么大O和大Ω失去他们的应用程序，因为我们是具体对此案和最多或至少有失去意义。我们可以简单地计算出T（N）或使用Θ，如果我们想成为粗糙。

On one hand just saying the running time of an algorithm without specifying the case complexity is ambiguous. On the other hand if it refers to one of these cases then the Big O and Big Ω lose their application, because we are specific on the case and at most or at least lose their meaning there. We simply can calculate the T(n) or use Θ if we want to be rough.

例如中的快速排序算法在平均情况下，时间是Θ（N LG N），并在最坏的情况下是Θ（N ^ 2）（我们可以计算出时间T（N） ）。然而，有些人可能带O指定它们（N日志N）和O（N ^ 2），而Θ也是正确的，更多的precise。

For example the time of quick sort algorithm in average case is Θ(n lg n) and in worst case is Θ(n^2) (as we can calculate the time T(n)). However, some may specify them with O(n log n) and O(n^2), but the Θ is also correct and more precise.

那么如何或为何要我们用O或Ω这个算法的运行时间？ 请不要忘了，包括这个问题的答案的具体实例。

Then how or why should we use O or Ω for the running time of this algorithm? Please don't forget to include the answer to this specific instance.

我不看的解释他们的，只是我们真的需要大O，而不是大Θ一些真实的例子。

推荐答案

偏小的答案

使用Θ时，它是已知的，因为它同时传达了关于O和Ω消息。不过你加倍你的是不正确像我的意见没有机会。当它不知道使用Ω

Use Θ when it is known because it conveys at the same time a message about O and Ω. Still you are doubling your chances of being incorrect like I did in the comments. When It is not known use Ω

龙的答案

这并不重要。什么是测量时，大O符号，案例分析在同一个问题空间的正交尺寸。

It doesnt matter. What is measured, the big O notation, the case analysis are orthogonal dimensions in the same problem space.

• 您可以做的最糟糕情况下的时间分析和限制的上限 0
• 您可以做的最好的情况下的空间分析，并提供 0 和下限Ω
• 您可以做摊销情况下的时间分析，并提供 0 和Ω，它变成这样是相同的提供了更紧密的结合Θ。

• You can do worst case time analysis and limit to the upper bound O
• You can do best case space analysis and provide O and lower bound Ω
• You can do amortized case time analysis and provide O and Ω, which turn out to be the same thus providing a tighter bound Θ.

现在提供的在最坏的情况下的运行时间的上界被分析的最流行的类型

Now providing upper bounds of the running time in worst case is the most popular type of analysis.

注意：的

Note:

如果您将得到一个家庭作业，它应该说明像

If you are given an homework, it should state something like

，这是什么算法在O.方面最坏情况下的时间复杂度

what is the worst case time complexity of this algorithm in terms of O.

如果您正在解决现实世界的问题，从问题本身推断这些。如果你的程序被终止，因为它使用了太多的内存，它没有任何意义做了运行时间复杂度分析。

If you are solving a real world problem, you infer these from the problem itself. If your program is killed because it uses too much memory, it doesn't make sense to do a running time complexity analysis.

要伸直，哪种符号（O，Θ或Ω），哪些时候就要   用于快速排序算法，为什么？

To be straight, which notation (O, Θ or Ω) and which time we should use for the time of the quick sort algorithm, why?

的后面是什么（O，Θ或Ω）？的

让我们说我们有像矩阵乘法一个有趣的问题。 人们发现，乘以矩阵将多个应用程序的帮助，所以他们开始寻找算法。

Let say we have a interesting problem like matrix multiplications. People find out that multiplying matrices will help in several applications, so they start looking for algorithms.

1. 在普通人ALG。设计师找到一个算法是为O（n ^ 3），用幼稚的方法。这并不是说效率低下，所以他上移动。
2. 在接下来施特拉森发现它可以提高到为O（n ^ 2.807）
3. 现在，人们开始问，如果它是可以进一步提高。
4. 在这个问题一部分是 如何进一步？的。要回复，您需要提供下界Ω。越高越好。一个约束是Ω（N ^ 2）。约束的具体Ω（N ^ 2的log（n））。他们不是通过提供的算法，但可以从问题陈述推导证明。
5. 现在，作为一个算法的设计师，如果你打一个上限 0的复杂性（N ^ 2的log（n））因为你知道你中奖矩阵计算。当你中奖了，你开始使用Θ传达两个信息一次。
6. 因为没有人中奖然而，在矩阵乘法算法的人EX preSS新发现更好的上限，如为O（n ^ 2.237）

1. The average joe alg. designer find an algorithm which is O(n^3), using the naive method. It is not that inefficient so he moves on.
2. Next Strassen find out that it can be improved to O(n^2.807)
3. Now people start to ask if it be can improved further.
4. A part of this question is how further ?. To reply, you need to provide lower bounds Ω. the higher the better. One bound is Ω(n^2). A specific bound of Ω(n^2 log(n)). They are not demonstrated by providing algorithms but can be deduced from the problem statement.
5. Now as an algorithm designer, if you hit a complexity of upper bound O(n^2 log(n)) for matrix computation you know you hit the jackpot. When you hit the jackpot, you start using Θ to convey two messages at once.
6. Because nobody has hit the jackpot yet,people express new findings in matrix multiplication algorithms in better upper bounds, like O(n^2.237)

的例子不同的下限在最坏的情况下 - 重新分配的数组的

An example of different lower bound in worst case - reallocation in arrays

假设你实施了一套使用数组。要插入你只是把下一个可用的桶一个元素。如果没有可用的桶增加阵列的容量值 M 。

Let's say you implement a set using an array. To insert a element you simply put in the next available bucket. If there is no available bucket you increase the capacity of the array by a value m.

有关插入算法的的没有足够的空间的是最坏的情况。

For the insert algorithm "there is no enough space" is the worse case.

 insert (S, e)
   if size(S) >= capacity(S) 
     reserve(S, size(S) + m)
   put(S,e)

假设我们从来没有删除元素。通过保持的最后一个可用的位置跟踪，把，尺寸和容量是Θ（1）在空间和内存。

Assume we never delete elements. By keeping track of the last available position, put, size and capacity are Θ(1) in space and memory.

什么储备？如果是喜欢 realloc的C语言实现，在最好的情况下，你只是在现有内存的末尾（储备最好的情况下）分配新的内存，或者你必须将所有现有的元素以及（储备最坏的情况）。

What about reserve? If it is implemented like realloc in C, in the best case you just allocate new memory at the end of the existing memory (best case for reserve), or you have to move all existing elements as well (worse case for reserve).

• 在最坏情况下界插入是最好的情况下， 储备（） ，这是线性的 M 如果我们不挑剔。 插入的 最坏的情况是Ω（M）在空间和时间。
• 在最坏的情况下上限为插入是最坏的情况下 储备（） ，这是线性的 M + N 。 插入在最坏的情况下是 O（M + N）在空间和时间。

• The worst case lower bound for insert is the best case of reserve(), which is linear in m if we dont nitpick. insert in worst case is Ω(m) in space and time.
• The worst case upper bound for insert is the worse case of reserve(), which is linear in m+n. insert in worst case is O(m+n) in space and time.

这篇关于大O或大Θ？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！