Question

O(2nlog(n));时间复杂度与O(nlog(n));小？为什么

Answer 1

这两个不是一样的么？……

追问

2nlog啊

追答

但是数量级相同啊

追问

那写个2代表啥意思？

追答

O(f(n))代表的意思是渐进上界，O(f(n))={g(n):存在正常数c和n0，使对所有的n>=n0，有0<=g(n)<=cf(n)}这个c对不同的函数f,g是可以换的，所以时间复杂度只看数量级啊~

追问

哥哥 我数学不太2 看不懂//能讲讲原理吗

追答

这么说吧g(n)=O(2nlog(n))代表的意思是 存在一个M>0 使得00使得0<=h(n)<=Knlog(n) 所以只需令K=2M就发现这两个本质上包含的函数类是相同的 也就是说 如果一个函数T(x)=O(2nlog(n))则必有T(x)=O(nlog(n)) 反过来也一样 所以这两个时间复杂度相同 你可以看看《算法导论》里面讲的很清楚的