大O还是大Θ？

Question

我知道Big O和BigΘ的区别,但我发现很少有我需要使用Big O或BigΩ而不是BigΘ的情况.

当给出算法以及运行时间复杂度(平均值,最差值和最佳值)的情况时,我们可以测量算法的运行时间并将其表示为Θ.(请注意算法意味着问题的清晰和一步一步的解决方案,如果我错了,请纠正我)

一方面,仅指出算法的运行时间而不指定案例复杂性是不明确的.另一方面,如果它指的是其中一种情况,那么Big O和BigΩ就会失去它们的应用,因为我们特定于案例,最多或者至少在那里失去意义.如果我们想要粗糙,我们可以简单地计算T(n)或使用Θ.

例如,平均情况下的快速排序算法的时间是Θ(n lg n),并且在最坏的情况下是Θ(n ^ 2)(因为我们可以计算时间T(n)).然而,一些人可以用O(n log n)和O(n ^ 2)来指定它们,但是Θ也是正确且更精确的.

那么我们应该如何或为什么要使用O或Ω作为该算法的运行时间？请不要忘记包含此特定实例的答案.

我不寻求对它们的解释,只是一些我们真正需要Big O而不是BigΘ的真实例子.

Answer 1

UmN*_*obe 5

偏小答案

?在知道时使用,因为它同时传达关于O和Ω的消息.你仍然像我在评论中那样加倍你不正确的机会.什么时候不知道用?

答案很长

没关系.测量的是big O notation,案例分析是同一问题空间中的正交维度.

现在,在最坏的情况下提供运行时间的上限是最流行的分析类型.

注意:

如果给你一个作业,它应该说类似的东西

根据O,该算法的最坏情况时间复杂度是多少.

如果您正在解决现实问题,可以从问题本身推断出这些问题.如果您的程序因使用太多内存而被终止,那么进行运行时复杂性分析就没有意义.

要直,哪种符号(O,Θ或Ω)以及我们应该在快速排序算法的时间使用哪个时间,为什么？

背后的理由是(O, ? or ?)什么？

假设我们有一个像矩阵乘法这样的有趣问题.人们发现乘法矩阵将有助于几个应用程序,因此他们开始寻找算法.

平均乔阿尔格.设计师O(n^3)使用天真的方法找到一种算法.这不是那么低效,所以他继续前进.
接下来斯特拉森发现它可以改进 O(n^2.807)
现在人们开始询问它是否可以进一步改善.
这个问题的一部分是如何进一步的？.要回复,您需要提供下限?.越高越好.一个界限是?(n^2).特定的界限?(n^2 log(n)).它们不是通过提供算法来证明的,而是可以从问题陈述中推断出来.
现在作为一个算法设计师,如果你达到O(n^2 log(n))矩阵计算上限的复杂性,你知道你中了大奖.当您获得累积奖金时,您开始使用?一次传达两条消息.
因为没有人赢得累积奖金,人们在矩阵乘法算法中以更好的上界表达新的发现,比如 O(n^2.237)

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

假设您使用数组实现了一个集合.要插入元素,只需将其放入下一个可用存储桶即可.如果没有可用的存储桶,则可以按值增加阵列的容量m.

对于插入算法,"没有足够的空间"是更糟糕的情况.

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

假设我们从不删除元素.通过保持最后一个可用位置的跟踪,put,size并且capacity是?(1)在空间和内存.

怎么样reserve？如果它像C中的realloc一样实现,在最好的情况下,您只需在现有内存的末尾分配新内存(保留的最佳情况),或者您也必须移动所有现有元素(更糟糕的情况是保留).

该下限为最坏的情况insert是最好的情况下 reserve(),这是线性的m,如果我们不挑剔.insert在最坏的情况下是?(m)在空间和时间.
的上限为最坏的情况insert是最坏的情况下 reserve(),这是在直链m+n.insert在最坏的情况下是 O(m+n)在空间和时间.