data-structures - d=θ(N) 在 d 堆中是什么意思，其中 N 是元素的数量？

Question

我想解决的问题：如果您必须在最初具有 N 个元素的 d 堆上执行 M 渗透和 N deleteMins。d=θ(N) 的运行时间是多少？

我对 d=θ(N) 的含义感到困惑。θ 应该表示平均案例运行时间，但在这种情况下，它用于表示 d 的值。

我的问题：我假设这意味着 d = N 所以这意味着实际的堆只是一个根，所有其他元素都连接到那个根。我的解释准确吗？

标签： data-structures

Answer 1

Big-theta 符号通常用于渐近运行时间，但它只是值和函数之间的关系，也可以在其他上下文中使用。

d=θ(N)表示存在常数a和b使得当N足够大时，aN < d < bN

显然，在这种情况下你不能有d > N，因为堆只有N个元素，但是一个常数可以任意小。例如，您可以有d = 0.1N。

问题的措辞表明，无论这些常数a和b是什么，渐近运行时间都是相同的，这对于答案是什么来说是一个很大的暗示。例如，您可以假设d = N，然后检查以确保在d = 0.1N时得到相同的答案。