关于查找N个数中的最大K个数的时间复杂度


在查找N个数中的最大的K个数的时候,可以维持一个小根堆。每次考虑一个数,如果比堆顶的数小则维持对不变;否则将其替代堆顶的元素,并调整堆。
当K也很大的时候,可以先尝试寻找最大的K'个数,然后查找第K'+1到第2*K'大的数,依次类推(容量为K'的堆可以完全装入内存)。
这样,要扫描所有数据的次数为什么是ceil(K/K')^2啊?

c 算法 C++

芙蘭朵露EX 11 years ago

Your Answer