二进制搜索+排序与线性搜索(大O)

Question

我对我正在处理的问题有疑问.我必须按顺序随机播放视频,而不重复播放视频.每个视频仅允许每个播放列表播放一次.每个视频都有一个从0到max_video_count的唯一ID,该id在运行时确定(取决于服务器).

我现在做的是,我创建了一个链接列表,添加了每个视频的唯一ID.比我在0和max_video_count之间随机创建一个随机数,如果数字已经在链表中则进行线性搜索,如果是,我计算一个新数字..再次线性搜索..等等!!

显然,这不是很实用,有时需要很长时间才能找到一个元素.特别是当很多视频播放时.

所以我想,我实现了线性搜索而不是线性搜索,但这让我想到了我必须首先对列表进行排序的问题.所以,我的下一步是思考,我在插入新的unique_id时对列表进行排序,而不是二元搜索.

我知道二进制搜索是O(log n)与O(n)线性搜索相比,这是一个很大的进步.但排序列表也是O(n)因为找到正确的位置我将不得不再做线性搜索.....所以我来解决方案比二进制搜索将是O(log N*n)相比较O(n)线性搜索 - >快速线性搜索.是对的吗？也许我的整个方法都是错的......但我还是想出更好的东西......

我对算法很新,所以如果有人能在这里启发我会很好:-)

问候马库斯

Answer 1

你基本上只是在看随机排列.将您的视频排列在一个固定列表中,然后创建播放列表,生成该列表的随机排列并播放置换列表.

实现这种置换的典型且有效的(O(n))方式是通过Knuth Shuffle.

_{(实际上,您当然可以创建索引集的随机排列,并按照置换索引的顺序播放项目.)}