相关疑难解决方法(0)

我目前正在学习Big O Notation运行时间和摊销时间.我理解O(n)线性时间的概念,意味着输入的大小成比例地影响算法的增长...例如,二次时间O(n ²)等也是如此.即使算法也是如此. ,例如置换生成器,具有O(n!)倍,通过阶乘生长.

例如,以下函数是O(n),因为算法与其输入n成比例增长:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

同样,如果有嵌套循环,则时间为O(n ²).

但究竟什么是O(log n)？例如,说完整二叉树的高度是O(log n)是什么意思？

我知道(可能不是非常详细)什么是对数,在这个意义上:log ₁₀ 100 = 2,但我无法理解如何识别具有对数时间的函数.

我很困惑,我认为你在最坏的情况下使用Big O运行时间,Ω是最好的情况？有人可以解释一下吗？

并不是(lg n)最好的情况？和(nlg n)是最坏的情况？还是我误解了什么？

表明在大小为n的堆上Max-Heapify的最坏情况运行时间是Ω(lg n).(提示:对于具有n个节点的堆,请提供节点值,以便在从根到叶子的路径上的每个节点上递归调用Max-Heapify.)

编辑:不,这不是功课.我正在练习,这有一个答案的关键买我迷茫. http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf问题4(6.2 - 6)

编辑2:所以我误解了不是关于Big O和Ω的问题？