我知道大O和大_的区别，但我发现很少有情况下我真的需要使用大O或大Ω而不是大_。
当算法以及运行时间复杂度（平均、最差和最佳）的情况下，我们可以测量算法的运行时间，并将其作为“状态”。（请注意，算法意味着一个问题的清晰和逐步的解决方案，如果我错了，请纠正我）
一方面，只在不指定情况复杂度的情况下说出算法的运行时间是不明确的。另一方面，如果它指的是其中的一种情况，那么大o和大Ω就失去了它们的应用，因为我们对这个情况是具体的，并且至少在那里失去了它们的意义。如果我们想粗略的话，我们可以简单地计算t（n）或使用_。
例如，在平均情况下，快速排序算法的时间是Θ（n lgn），在最坏情况下是Θ（n^2）（因为我们可以计算时间T（n））然而，有些人可能会用o（n logn）和o（n^2）来指定它们，但_也是正确和更精确的。
那么我们应该如何或者为什么使用O或者Ω来计算这个算法的运行时间呢？
请不要忘记包含此特定实例的答案。
我不想解释它们，只是一些真正的例子，我们真的需要大O而不是大Θ。
最佳答案
部分小答案
已知时使用Θ，因为它同时传送关于o和Ω的消息。但你还是加倍了你被错误的机会，就像我在评论中所做的那样。当未知时，使用Ω
冗长的回答
没关系所测量的是，在同一问题空间中的big O notation，案例分析是正交维度。
您可以进行最坏情况时间分析，并限制在上限O
您可以进行最佳案例空间分析，并提供O和下限Ω
您可以进行分期案例时间分析，并提供O和Ω，结果是相同的，因此提供了一个更严格的界限Θ。
现在，在最坏的情况下提供运行时间的上限是最流行的分析类型。
笔记
如果给你一个家庭作业，它应该说明
什么是最坏情况下该算法的时间复杂度的O。
如果你正在解决一个现实世界的问题，你可以从问题本身推断出这些如果程序由于使用过多内存而被杀死，那么执行运行时复杂度分析就没有意义了。
直截了当地说，我们应该用什么符号（O，Θ或Ω）和什么时间
用于快速排序算法的时间，为什么？(O, Θ or Ω)背后的基本原理是什么？
假设我们有一个有趣的问题，比如矩阵乘法。
人们发现乘法矩阵在一些应用中有帮助，所以他们开始寻找算法。
一般的乔·阿尔格设计器使用naive方法查找O(n^3)的算法。没有那么低效，所以他继续前进。
接下来Strassen发现它可以改进为O(n^2.807)
现在人们开始问它是否可以进一步改进。
这个问题的一部分是如何进一步？。若要答复，您需要提供下限Ω越高越好一个界限是Ω(n^2)Ω(n^2 log(n))的特定界限。它们不是通过提供算法来演示的，而是可以从问题陈述中推导出来的。
现在，作为一个算法设计者，如果你碰到了矩阵计算的上界O(n^2 log(n))的复杂性，你就知道你的头奖了。当你中大奖时，你开始使用Θ同时传递两条信息。
因为还没有人中大奖，人们在矩阵乘法算法中用更好的上界来表达新的发现，比如O(n^2.237)
最坏情况下不同下限的一个例子-数组中的重新分配
假设您使用数组实现一个集合要插入元素，只需将其放入下一个可用的bucket中如果没有可用的bucket，可以将数组的容量增加一个值m。
对于insert算法，“没有足够的空间”是更糟糕的情况。
insert (S, e)
if size(S) >= capacity(S)
reserve(S, size(S) + m)
put(S,e)
假设我们从不删除元素。通过跟踪最后一个可用位置，
put、size和capacity在空间和内存中都是Θ(1)。那
reserve呢？如果它像realloc in C那样执行，在最好的情况下，您只需在现有内存的末尾分配新的内存（保留的最佳情况），或者您还必须移动所有现有元素（更坏的情况下为保留）。insert的最坏情况下界是reserve()，如果我们不挑剔，它在m中是线性的。insert英寸最坏的情况是在空间和时间上
Ω(m)。insert的最坏情况上限是reserve()，在m+n中是线性的insert最坏的情况是在空间和时间上。
关于algorithm - 大O还是大Θ？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26486027/