O(V/2^k*log(V/2^k) + kE)的最小时间复杂度

bankrock · #1 (**permalink**) 2007-10-04

这里k是一个可任选的迭代次数，V和E是一个图的顶点数和边数。取那个k可以使O(V/2^k*log(V/2^k) + kE)的值最小呢？

cat · #2 (**permalink**) 2007-10-04

对k求个导=0? 忘记怎么求了……

bankrock · #3 (**permalink**) 2007-10-05

我就是这么做的，算不出来啊，求了导还有log，是个隐函数。
结果应该是O(E*log(logV)) ) （如果我之前的推导没错的话），烧卖快来救救我

polyrandom · #4 (**permalink**) 2007-10-05

你怎么知道我早晨吃的烧卖？还在我肚子里呢。

bankrock · #5 (**permalink**) 2007-10-05

管理员居然把版主吃了，天理何在？赶紧吐出来

Elminster · #6 (**permalink**) 2007-10-07

引用:

作者: polyrandom

你怎么知道我早晨吃的烧卖？还在我肚子里呢。

就澳大利亚那个鸟不拉屎的地方，你还能找到烧卖当早餐？少扯淡了 ……

引用:

作者: bankrock

这里k是一个可任选的迭代次数，V和E是一个图的顶点数和边数。取那个k可以使O(V/2^k*log(V/2^k) + kE)的值最小呢？

你这个 k 是与 V 和 E 无关的常数？是 V 的函数？是 E 的函数？还是二者的函数？你这个图里面 V 和 E 的关系大概是什么样子？E 是 O(V) 这个量级还是 O(V^2) 这个量级？

bankrock · #7 (**permalink**) 2007-10-07

V和E当常数看，E=O(V) (Very sparse graph)。

Elminster · #8 (**permalink**) 2007-10-07

引用:

作者: bankrock

V和E当常数看，E=O(V) (Very sparse graph)。

k 和 V/E 无关？那这不就是一元函数求极值么？求导算拐点，机械步骤就是了吧？

bankrock · #9 (**permalink**) 2007-10-15

这里的一元函数是xlogx型的，一次求导没解析结果的啊？

Elminster · #10 (**permalink**) 2008-01-20

引用:

作者: bankrock

这里的一元函数是xlogx型的，一次求导没解析结果的啊？

怎么会？log(V/2^k) = log(V) - k 啊。解开来是代数式子吧？

bankrock · #11 (**permalink**) 2008-01-23

大哥，这个式子还要除2^k呢

Elminster · #12 (**permalink**) 2008-02-02

引用:

作者: bankrock

大哥，这个式子还要除2^k呢

...
未老先衰啊，眼神一塌糊涂了。不过话说 ... PORA！当初这里不是支持 latex 的么？
好吧，这个解析式子大概是解不出来了，上迭代吧，

polyrandom · #13 (**permalink**) 2008-02-03

引用:

作者: Elminster

...
未老先衰啊，眼神一塌糊涂了。不过话说 ... PORA！当初这里不是支持 latex 的么？
好吧，这个解析式子大概是解不出来了，上迭代吧，

我亲爱的早饭，目前这里还是支持latex的。