c++ - 对于给定的方程 f(N)，满足 O(f(N)) 意味着什么？

Question

这是我最后的评论中唯一一个我仍然不确定的问题。我已经弄清楚了所有其他 74 个，但这一个完全难倒我。我认为这与找到 C 和 k 有关，但我不记得如何做到这一点或它甚至意味着什么……而且我什至可能不在正确的轨道上。

我遇到的问题是“N 的最小可接受值是多少，才能O(f(N))满足成员函数的定义Heap::Insert(int v)？”

Heap::Insert(int v) 的代码如下：

void Insert(int v) 
{ 
  if (IsFull()) return; 
  int p=++count; 

  while (H[p/2] > v) { 
     H[p] = H[p/2]; 
     p/= 2; 
  } 
  H[p] = v; 
}

给出的可能答案是：32, 64, 128, 256。

我完全被难住了，必须在早上参加这次考试。帮助将不胜感激。

score 1 · Accepted Answer

我承认这个问题很模糊，但我会尽力给出一个合理的解释。

如果我们f(N)将代码执行的操作的时间复杂度称为堆中元素数量的函数，教授希望您记住f(N) = O(log(N))对于二进制堆插入，即是O(h)堆h的高度，我们假设它是完整的（记住堆的工作原理以及它可以表示为二叉树）。因此，您必须尝试这四个值Nmin并找到满足定义的最小值，即

f(n) <= k*log(N)

对于每个N >= Nmin并且至少一个 k. f(N)如果只有您的代码完成了教授或您期望它执行的操作，我会为您提供计算的详细信息。

注意：我真的很喜欢在 Stack Overflow 问题上使用 LaTeX 渲染！就像在数学上

1 回答 1