V2EX › jedihy 的所有回复 › 第 72 页 / 共 117 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

1 ... 68 69 70 71 72 73 74 75 76 77 ... 117

❮

❯

2016-12-26 14:12:05 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

@lxiange 你依然还是不明白什么是 n ，什么是 the length of the string representing the input ，这些都基于你怎么定义的。在没有明确定义 n 的时候， O(2^n) has nothing to do with the given program.

2016-12-26 14:09:04 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

就算在顶级的 TCS 期刊， TALG 和 TOCS 上，都会简易的指出该算法的时间复杂度是 O(n)，这决定于 n 是怎么定义的。你可以考到大多数 NPC 问题的伪多项式时间算法的 big O 都是这么标注的，如背包， subset sum partition 。当然你说 O(2^n)也是绝对正确，但一切的前提是你必须给出一个严格的定义， O(2^n)这个结论本身就是基于很多严谨的假设基础上才得出的，你不能随便一指就说是 O(2^n)。

2016-12-26 13:59:37 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

他的时间复杂度不管怎么算，最会都会等于 O(2^m) = O(n)。

2016-12-26 13:58:34 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

这个不管是怎样的，你都不能说 O(n)是错的，如果 n == variable in the input

2016-12-26 07:39:32 +08:00

回复了 imcczy 创建的主题 › 问与答 › 研究生读的很抑郁，想退学了，求指导

rank3 是什么意思，没明白， CCF C 类？还是排名第三的期刊会议？

2016-12-26 06:03:56 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

@lxiange 不过是从算法理论角度还是其他角度，你都错了，你重定义了 n 。
他的时间复杂度是可以等于 O(2^m)，但是 m = log_2 n = maximum number of bits in variable n 。
O(2^m) = O(2^(log_2 n)) = O(n)，证毕。

2016-12-26 05:58:22 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

@xupefei 确实是输入长度的限制，这个算法导论上有。这个地方楼主是偷换概念了，我说这个东西时间复杂度是 O(n)是绝对没错的。如果说它的时间复杂度是 o(2^n)，你必须给出 n 的严格定义，不能偷偷把 n 的定义给换了。

2016-12-26 02:46:30 +08:00

回复了 WINGO 创建的主题 › MacBook Pro › 买了 2016 新款 MBP 的 V 友，来说说你们买的 type-c 扩展坞吧

anker hdmi 有问题

2016-12-26 01:33:52 +08:00

回复了 jedihy 创建的主题 › MacBook Pro › 2016 mbp15 订制顶配打 dota2 中效都有点卡

Windows 下确实好很多， vulkan 没有 dx 帧数高

2016-12-26 00:21:29 +08:00

回复了 lxiange 创建的主题 › 程序员 › 来看看这个函数的时间复杂度是多少

O(n)