时间复杂度是多少
(1) 随机打乱一个长度为 N 的列表？
(2) 从 N 个项目中随机选择一个项目 N 次？
问问题
474 次
2 回答
2
取决于您的洗牌算法和预期的行为。例如，iTunes shuffle 会在您随机播放时创建一个备用播放列表顺序，从而立即随机播放所有歌曲，但也会创建一个可重复的播放列表顺序（如果您听了两次播放列表，相同的歌曲将相互跟随），但如果您想要您可以在每首歌曲之前选择一个新种子，并在您开始播放时通过选择真正随机播放曲目。然而，时间复杂度对于两者来说基本上是相同的，在任何一种情况下都可以忽略不计。
然而，理论上，它们都是 O(nr) 时间复杂度（其中 r 是随机数算法的时间复杂度）。
于 2012-08-23T18:57:33.620 回答
1
洗牌一个列表是 O(n)
从大小为 n 的列表中随机选择 n 个东西也是 O(n)
您可能最好在每次播放时随机选择一些东西，因为歌曲列表不一定会永远保持不变。在这种情况下，必须重做预计算。
于 2012-08-23T21:30:42.500 回答