首页 > 试题广场 >

对于n个带权样本的随机有放回带权采样，采样m次。最优时间复杂

[单选题]
对于n个带权样本的随机有放回带权采样，采样m次。最优时间复杂度为？ 
  • O(m)
  • O(n+m)
  • O(mlogn)
  • O(n*m)
查看正确选项
添加回答
YwandungLyou头像 YwandungLyou
没想明白，谁知道请分享思路。
发表于 2021-07-31 21:59:48 回复(0)
wwwwwizkd头像 wwwwwizkd
自己的思路 不知道对不对
统计n个样本的权，排序 ，存在哈希表里，O(n)
之后每次生成一个随机数，通过哈希表直接得到指定权重位次的样本。
一共m次 O(m)
所以最后O(m+n)
发表于 2021-08-05 16:52:52 回复(0)
提交观点

问题信息

算法工程师 哔哩哔哩 2021
上传者：小小
难度：
2条回答 517浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号