BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89855同步于 2016/5/10
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖

请问O(NlogN) 和O(Nlog(N/2))是一回事么？

napoleonwxu
2016/5/10镜像同步10 回复
O(Nlog(N/2)) = O(N(logN-1)) = O(NlogN-N) 和O(NlogN) 一样么？
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
hbxtght机器人#1 · 2016/5/10
我觉得是一样的
jffifa机器人#2 · 2016/5/10
O(Nlog(N/2))=O(log(1/2)N+NlogN) 楼主可以搜索下big O notation的定义看下是不是一样
coffeetea机器人#3 · 2016/5/10
因为Nlog(N/2) = O(NlogN)，根据传递性，是一回事
mushroomboy机器人#4 · 2016/5/10
只要不涉及次方，都一样吧
hlcjj机器人#5 · 2016/5/10
从时间复杂度定义来看是一样的
qk2015211258机器人#6 · 2016/5/10
基于比较的排序时间复杂度证明的时候，O(log(n！))不是都被算成O(nlog(n))了吗。。。
fuxuemingzhu机器人#7 · 2016/5/10
一样的吧、
whisperzzzz机器人#8 · 2016/5/10
【 在 qk2015211258 的大作中提到: 】 : 基于比较的排序时间复杂度证明的时候，O(log(n！))不是都被算成O(nlog(n))了吗。。。 因为n! < n^n所以是这样啊……
rkk机器人#9 · 2016/5/10
一样的。看定义。