什么被认为是图形算法的渐近改善？

Question

让我们说我们正在尝试解决一些算法问题 $ a $ ，它取决于大小的输入 $ n $ 。 我们说算法 $ b $ 运行时间 $ t（n）$ ，比算法更好 $ c $ ，它以时间为 $ g（n）$ 如果我们有： $ g（n）= o（t（n））$ ，但 $ t（n）$ 不是 $ o（g（n））$ 。

我的问题与图算法的渐近运行时间有关，它通常依赖于 $ | v | $ 和 $ | e | $ 。 具体而言，我想专注于prim的算法。如果我们使用二进制堆实现优先级队列，则运行时将是 $ o（e \ log v）$ 。使用fibonacci堆，我们可以获得 $ o（v \ log v + e）$ 的运行时。

我的问题是我们说 $ o（v \ log v + e）$ 渐近地比 $ o（e \ log v）$ ？

让我澄清：我知道如果图表密集答案是肯定的。但是，如果 $ e= o（v）$ 两个解决方案是相同的。 我对通常的定义是渐近的改进，因为我们有多个变量的渐近改善，甚至更糟糕 - 变量不是独立的（ $ v-1 \ le e ，因为我们假设图表是针对prim的算法连接的）。

谢谢！

Answer 1

最允许的定义如下。

假设 $ f（v，e），g（v，e）$ 是图形算法的两个运行时间，解决了相同的问题。

我们说 $ f $ 是某些制度上的渐近改进 $ g $ 如果存在序列 $ v_n，e_n $ 与 $ v_n \ to \ idty $ 这样的 $$ \ lim_ {n \ to \ idty} \ frac {f（v_n，e_n）} {g（v_n，e_n）}= 0。 $$

有时政权没有被视为有趣，但这是一个更主观的事情。

还要注意，问题已经表明了一个变量函数本身。考虑 $$ f（n）= n ^ 2，\ qquad g（n）=begin {is} 2 ^ n＆\ text {if} n= 2 ^ m，\\ n＆\ text {否则}。 \结束{案例} $$ $ f $ 通过 $ g $ 的渐近改进？它是一定长度的输入，并且确实如此在我们上面的允许定义下。