Question

从堆中删除一个元素的时间复杂度是多少？麻烦解释一下

Answer 1

每次调整至少能排除一半的个数(从x到其x-1层,x层得个数应该是所有个数的一半+1),所以复杂度是log级别

追问

哥们 你算的很对 但是我没看懂 为什么是 用log

追答

比如有32个元素(为了方便取一个2的幂), 第一次排除 ,16,第二次,8,第三次4,... 2,1. 以这种规律排除几次才能完呢?
比如要排除a次,那么 第一次 2^(a-1) ,第二次2^(a-2)... 第三次2^(a-3) ....第a次2^0=1
是不是 总的个数-1= 1+2+4+...2^(a-1) =2^a-1
那么总的个数=2^a 所以: a=log2 (总的个数)
呵呵...

Answer 2

n/2就是o(n)啊，呵呵。计算方式就是这样的，如果有一个n，那就是n，即存在一个k，k只要是常数k，那么kn的时间复杂度就是o(n)，如果有两个n，那就是o(n^2)了。