gpt4 book ai didi

algorithm - 寻找具有次线性空间复杂度的中位数的在线算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:51:50 24 4
gpt4 key购买 nike

有一项任务是规划一个算法/数据结构,该算法/数据结构可以一个一个地接收值,并可以在被询问时给出当前的中位数。应支持时间复杂度logn的值求值,并输出时间复杂度恒定的中位数。

有没有办法用次线性空间复杂度做到这一点?谢谢。

最佳答案

如果您已经看到 n 个数字,则可以通过添加更多数字来使每个数字成为当前中位数。因此不可能找到亚线性空间复杂度的解。

关于algorithm - 寻找具有次线性空间复杂度的中位数的在线算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48500675/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com